Scrambler: Mixed Boolean Arithmetic Obfuscation Tool Using E-graph and Equality Expansion

이 논문은 동등성 확장을 기반으로 한 E-graph 를 활용하여 구성 단계에서 동등성이 보장되는 복잡하고 다양한 혼합 부울 산술 (MBA) 식을 효율적으로 생성하는 'Scrambler'라는 새로운 난독화 도구를 제안하고, 기존 도구보다 표현력과 복잡성이 향상되었음을 실험을 통해 입증합니다.

핵심

📜 "스캠블러 (Scrambler)": 코드를 숨기는 마법의 요리사

이 논문은 프로그램을 해킹하거나 분석하기 어렵게 만드는 기술에 대한 이야기를 담고 있습니다. 마치 요리사가 맛있는 요리를 만들되, 그 레시피를 알 수 없게 만드는 것과 비슷하죠.

이 기술을 설명하기 위해 세 가지 핵심 개념을 일상적인 비유로 풀어보겠습니다.

---

1. 문제: "너무 쉬운 요리 레시피" (기존 기술의 한계)

지금까지 코드를 복잡하게 만드는 도구들은 **정해진 레시피 (규칙)**만 사용했습니다.

• 비유: 요리사가 "소금만 넣는 법", "설탕만 넣는 법" 같은 단순한 레시피만 가지고 있습니다.
• 결과: 해커들이 이 레시피를 외우면, 요리 (코드) 가 어떻게 만들어졌는지 금방 알아차리고 맛 (기능) 을 그대로 복원해버립니다. 또한, 만들 수 있는 요리 종류도 제한적입니다.

2. 해결책: "스캠블러 (Scrambler)"라는 새로운 요리사

이 논문에서 제안한 **'스캠블러'**는 기존 도구들과 완전히 다른 방식을 사용합니다.

🧩 비유 1: "동일한 맛을 가진 재료들" (E-Graph)

스캠블러는 코드를 단순한 나열이 아니라, **모든 가능한 변형이 동시에 연결된 거대한 그물망 (E-Graph)**으로 봅니다.

• 상황: "소금 1g"과 "간장 1방울"이 같은 맛을 낸다고 가정해봅시다.
• 기존 방식: 소금만 넣거나 간장만 넣는 두 개의 다른 요리를 따로 만들어야 합니다.
• 스캠블러 방식: 그물망 안에 "소금"과 "간장"을 **같은 그릇 (E-class)**에 넣어둡니다. "이 두 재료는 맛 (의미) 이 똑같아!"라고 표시해두는 거죠. 이렇게 하면 코드를 분석할 때 어떤 재료를 썼든 결과는 똑같다는 것을 보장받습니다.

🌪️ 비유 2: "맛을 더하는 마법" (Equality Expansion)

기존 도구는 "최단 경로"를 찾아 요리를 빨리 끝내려 했지만, 스캠블러는 의도적으로 요리를 복잡하게 만듭니다.

• 목표: "이 요리는 1000 개의 재료가 들어갈 때까지 계속 변형시켜!"
• 과정:
  1. 간단한 요리 (예: $x + y$) 를 그물망에 넣습니다.
  2. "소금 = 간장", "설탕 = 꿀" 같은 변환 규칙을 계속 적용합니다.
  3. 그물망 안에서 재료를 갈아치우며 요리를 점점 더 복잡하고 거대하게 만듭니다.
  4. 중요한 점: 재료가 아무리 많이 변해도, 원래 맛 (기능) 은 절대 변하지 않습니다.

3. 왜 이것이 대단한가요? (실험 결과)

연구팀은 스캠블러와 기존 도구들을 비교 실험했습니다.

비교 항목	기존 도구 (NeuReduce, Loki 등)	스캠블러 (Scrambler)
요리 크기 (복잡도)	중간 정도 (재료가 20~200 개)	엄청나게 큼 (재료가 3 만 개 이상!)
다양성	제한된 레시피만 사용	무한한 변형 가능
안전 확인	요리가 망가졌는지 한 번 더 확인 필요 (시간 걸림)	원래 맛 보장됨 (확인 불필요, 빠름)

• 결과: 스캠블러는 기존 도구보다 수천 배 더 복잡한 코드를 만들 수 있었습니다. 해커가 이 코드를 뒤집어보려고 해도, 그 복잡함 때문에 포기하게 만들 가능성이 큽니다.

4. 핵심 요약: "왜 스캠블러가 특별한가?"

1. 보장된 맛 (Equivalence Guaranteed): 코드를 아무리 복잡하게 변형해도, 프로그램이 원래 하던 일을 절대 망치지 않습니다. 그물망 구조 덕분에 변형 과정에서 실수가 날 수 없기 때문입니다.
2. 검증 불필요: 기존 도구는 "이 복잡한 코드가 원래 코드랑 같은가?"를 확인하기 위해 무거운 계산기를 (SMT 솔버) 써야 했지만, 스캠블러는 구조상 이미 같은 것이 보장되어 있어 확인 과정이 필요 없습니다.
3. 압도적인 복잡도: 적은 규칙 (약 14 가지) 만으로도 거대한 규모의 복잡한 코드를 순식간에 만들어냅니다.

🎁 결론

이 논문은 **"코드를 해커에게 숨기는 새로운 마법"**을 소개합니다.
기존에는 "단순한 규칙"으로 코드를 숨겼다면, 스캠블러는 "동일한 의미를 가진 수만 가지 변형"을 그물망으로 연결해 해커가 감당할 수 없을 정도로 복잡한 코드를 만들어냅니다.

마치 단순한 소금 한 알을, 수만 개의 다른 조미료 조합으로 변신시켜도 결국 같은 짠맛을 내는 마법과 같습니다. 덕분에 프로그램은 여전히 잘 작동하지만, 누가 만들었는지, 어떻게 작동하는지는 영원히 알 수 없게 됩니다.

기술 요약

논문 요약: Scrambler (E-Graph 및 Equality Expansion 기반 MBA 오프스큐레이션 도구)

1. 문제 정의 (Problem)

• 배경: 프로그램 오프스큐레이션 (Obfuscation) 은 분석을 어렵게 하기 위해 기능적으로 동일하지만 가독성이 낮은 형태로 코드를 변환하는 기술이다. 그중 혼합 부호 - 산술 (Mixed Boolean-Arithmetic, MBA) 오프스큐레이션은 적용 비용이 상대적으로 낮고 역분석에 대한 저항력이 높아 널리 사용된다.
• 기존 기술의 한계:
  • 기존 MBA 오프스큐레이션 도구 (MBA Obfuscator, NeuReduce, Loki 등) 는 미리 정의된 MBA 규칙과 특정 행렬 기반 정보 (진리표, 선형 대수 표현 등) 에 의존한다.
  • 이로 인해 생성 가능한 MBA 식의 다양성이 제한된다.
  • 연산자 (Operator) 지원 범위가 좁고, 복잡한 식 생성 시 과도한 오버헤드가 발생하며, 확장성 (Scalability) 이 부족하다.
  • 생성된 식의 동치성 (Equivalence) 을 검증하기 위해 Z3 와 같은 SMT 솔버를 사용하는 경우가 많으나, 대규모 또는 복잡한 MBA 식에서는 성능이 급격히 저하된다.

2. 방법론 (Methodology)

저자들은 Scrambler라는 새로운 MBA 오프스큐레이션 도구를 제안하며, 이는 E-Graph 데이터 구조와 Equality Expansion (등식 확장) 기법을 핵심으로 한다.

• E-Graph (Equivalence Graph):
  • 동등한 의미를 가진 표현들을 별도의 노드가 아닌 동일한 'e-class'로 그룹화하여 그래프 내에 동시에 표현하는 자료구조이다.
  • 이를 통해 중복 표현을 제거하고, 여러 동치인 식을 하나의 그래프 구조로 효율적으로 관리할 수 있다.
• Equality Expansion (등식 확장):
  • 기존 최적화 알고리즘인 'Equality Saturation (등식 포화)'를 변형한 개념이다.
  • Equality Saturation: 주어진 규칙을 적용하여 가능한 모든 경우를 탐색한 후, 가장 간단한 식을 찾는 것을 목표로 함.
  • Equality Expansion: 주어진 규칙을 적용하여 복잡한 식을 생성하는 것을 목표로 함.
    • 종료 조건을 '가장 간단한 식 찾기'가 아닌, 'AST 크기 초과 (예: 1000 노드 이상)', '탐색 시간 제한', '규칙 적용 횟수' 등으로 설정하여 단순한 식을 복잡한 식으로 변환한다.
• 구현:
  • Rust 기반의 egg 프레임워크를 사용하여 구현됨.
  • 입력: 규칙 집합 (Rule Set), 오프스큐레이션 대상 식, 종료 조건.
  • 출력: 조건을 만족하는 가장 복잡한 MBA 식.
  • 동치성 보장: E-Graph 와 규칙 기반 변환의 특성상, 입력 규칙의 의미론적 동치성이 보장되면 생성된 MBA 식은 별도의 검증 (SMT 솔버 등) 없이도 자동으로 동치성이 보장됨.

3. 주요 기여 (Key Contributions)

1. Scrambler 도구 개발: E-Graph 와 Equality Expansion 기법을 활용한 새로운 MBA 오프스큐레이션 도구 제안.
2. 표현력과 복잡성 향상: 기존 도구들이 가진 연산자 제한과 식 다양성 한계를 극복하고, 선형, 다항식, 비다항식 등 다양한 유형의 MBA 식을 생성 가능.
3. 검증 과정 제거: 생성된 식의 동치성을 E-Graph 구조가 내재적으로 보장하므로, 별도의 SMT 솔버를 이용한 검증 단계를 생략하여 생성 효율성을 극대화함.
4. 확장성: 사용자 정의 규칙을 통해 복잡한 식을 빠르게 생성할 수 있는 구조를 제공.

4. 실험 결과 (Results)

Scrambler 를 기존 도구 (NeuReduce, Loki, MBA Obfuscator) 와 비교 평가한 결과, 다음과 같은 수치를 기록함 (평균값 기준):

지표 (Metric)	NeuReduce (Obfuscated)	Loki (Obfuscated)	MBA Obfuscator (Obfuscated)	Scrambler (Obfuscated)
AST 크기 (Size)	23.85	216.17	235.22	34,786.77
연산자 수 (# Op)	13.31	142.82	136.22	23,373.46
MBA 교대 (Alternation)	3.89	38.26	31.83	6,387.58
엔트로피 (Entropy)	3.11	2.66	3.12	2.59

• 구조적 복잡성: Scrambler 는 약 14 개의 규칙과 3,000 노드 확장 제한만으로도 기존 도구들보다 훨씬 더 거대한 AST 크기와 연산자 수를 가진 식을 생성함.
• 효율성: 별도의 검증 단계가 없어 생성 속도가 빠르며, 메모리 및 규칙 제약 내에서 원하는 복잡도까지 식을 확장 가능.
• 규칙 의존성: 단일 연산자와 관련된 규칙 수를 증가시키면 특정 임계값을 넘어서면 메트릭 (복잡도) 이 급격히 증가함을 확인함.

5. 의의 및 결론 (Significance & Conclusion)

• 기술적 의의: MBA 오프스큐레이션 분야에서 E-Graph 와 Equality Expansion 기법을 성공적으로 적용하여, 기존 도구들의 한계였던 '생성 식의 다양성 부족'과 '검증 오버헤드' 문제를 동시에 해결함.
• 실용성: 생성된 식이 수학적으로 동치임이 보장되므로, 보안 분석가에게 더 강력한 난독화 (Robust Obfuscation) 를 제공할 수 있음.
• 향후 과제: 적용된 규칙의 정확성을 신중하게 검증해야 하며, 규칙 선택에 따른 성능 변동성을 관리해야 함. 또한 메모리 제약과 규칙 제약 사이의 균형을 맞추는 것이 향후 연구 방향.

이 논문은 오프스큐레이션 기술의 새로운 패러다임을 제시하며, 특히 복잡한 논리 구조를 가진 코드를 보호하는 데 있어 기존 방법론보다 우월한 성능을 입증하였다.