스마트 퍼저의 혁명(The Smart Fuzzer Revolution)

출처 : https://blog.trailofbits.com/2017/02/16/the-smart-fuzzer-revolution/

---

Trail of Bits 팀이 BSidesLisbon 에서 스마트 퍼징(smart fuzzing)에 대해 발표를 했다.
최근, CGC, AFL, libFuzzer 등이 개발되면서 취약점 자동 탐지 분야가 빠르게 성장하고 있다.
이러한 연구 분야가 어디에서 왔고, 현재의 위치는 어떠하고, 어떻게 발전할 지 간단하게 알아보자.

---

Indroduction

지난 2년(2015~2016) 동안 보안 테스트 자동화(automated security testing)은 빠르게 성장했다.
AFL(American Fuzzy Lop) 은 사용하기 쉬운 실용적인 도구로 알려졌으며,
DARPA Cyber Grand Challenge 는 신뢰할 수 있는 벤치마크를 제공했을 뿐 아니라 새로운 연구를 위한 자본을 지원했다.
Project Springfiled (aka SAGE) 는 이제 공개됐다. 이러한 새로운 기술의 보급은 업계에 큰 영향을 줄 가능성이 높다.

이러한 도구들은 어떻게 동작하며, 과거의 접근 방식과 다른점은 무엇일까? 그리고 어떤 부분에서 효과적이고, 한계점은 무엇일까? 우리는 이 도구를 어떻게 활용할 수 있을까? 이러한 도구들은 어떻게 발전할 것이며, 앞으로 개선되어야 할 점은 무엇일까?

이에 대한 키노트와 슬라이드는 다음 링크에서 확인할 수 있다.

video : https://www.youtube.com/watch?v=g1E2Ce5cBhI
slide : https://docs.google.com/presentation/d/1FgcMRv_pwgOh1yL5y4GFsl1ozFwd6PMNGlMi2ONkGec/edit#slide=id.g13a9c1bce4_6_0

---

The Smart Fuzzer Revolution

Brief History

In the Beginning

정상적인 입력(well-formed inputs)에 랜덤 뮤테이션을 적용하고, 결과를 관찰한다.

• Random: “cat /dev/urandom | program”

  • Class assignment in “Advanced Operating Systems” at University of Wisconsin (1988)

• Generation: Write a BNF spec -> introduce anomalies

  • PROTOS from OUSPG (2002) & Block-based Fuzzing from Dave Aitel (2002)

• Mutation: Assemble valid input corpus -> introduce anomalies

  • Eg. radamsa, zzuf, etc

Random: 상태(state)나 구조(structure)에 무관하게 무작위로 수행하며, 제공한 것과 같은 결과를 얻을 것을 기대한다. 놀랍게도 매우 효과적이다.
Generate: 프로그램이 기대하는 데이터 구조를 생성한다. (SPIKE + Shellcoder’s Handbook 참조)
Mutation: 리소스 집약적(resource-intensive) — 정상적인 데이터의 거대한 코퍼스를 재조립한다.

Iterative Advances

• 적용 범위를 설정하고, 최소화된 입력 집합 생성
• 크래시를 발생한 입력을 이용해 다시 퍼징 (“rocket-propelled chainsaw”)
• 휴리스틱을 통한 크래시 분류 시도
• 테스트케이스 생성을 위한 심볼릭 실행(symbolic execution) 및 SMT 솔버를 결합하려는 초기 시도 (EXE(2006), DART(2005))
  • EXE/DART는 concrete-symbolic execution과 경로 제거(path pruning)를 KLEE에 도입했다.
• SMT 솔버의 진보 (Z3)

Ref 1: http://web.stanford.edu/~engler/exe-ccs-06.pdf
Ref 2: https://wkr.io/public/ref/godefroid2005dart.pdf

Enter Smart Fuzzing

• Microsoft Research는 2008년에 스마트 퍼징을 세상에 도입했다.

  • Scalable, Automated, Guided Execution (SAGE) in “Automated Whitebox Fuzz Testing”
  • SAGE는 덤 퍼징(domb fuzzing)이 끝나는 지점과 스마트 퍼징이 시작하는 지점을 명확히 선정한다.

• Key advance: 퍼징과 심볼릭 실행을 결합하여 새로운 테스트를 동적으로 생성하고, “상태 폭발(state explosion)” 문제를 관리한다.

  • 실행을 기록하고, 새로운 제약조건(constraints)을 수집하기 위해 추적을 심볼릭하게 평가한다.
  • 제약조건 해결자(constraint solver)를 사용해 새로운 제어 경로를 새로운 입력을 생성한다.
  • 최대 테스트 깊이를 달성하는 새로운 입력의 순위 선정을 위해 코드 커버리지를 측정한다.

SAGE Benifits

SAGE: easy to use, available

• Key benifits

  • if(x+y==z) 와 같은 Pre-SAGE 문장이나 간단한 체크섬은 퍼저를 방해한다. SAGE는 이를 쉽게 해결하고, 새로운 입력을 찾을 수 있다.

• Sage works in the real world

  • 바이너리에서 동작하며, 소스코드가 필요하지 않다.
  • 실제적이며, 큰 애플리케이션을 처리한다.
  • 초기 입력값이나 문법 등의 정보가 필요하지 않다.
  • 오탐(false positive)가 없다. 실제 버그를 찾으며, 이를 트리거하는 입력을 생성한다.

AFL

AFL은 SAGE에 비해 똑똑하진 않다. 하지만 이는 오히려 효과적이다.

• Major contributions
  • 코드 커버리지를 측정하기 위해, 컴파일러를 통한 계측(instrumentation)을 삽입한다.
  • 퍼징을 유도하기 위해 코드 커버리지를 사용한다.
  • 빠르고 쉬운 병렬 처리가 가능하다. (compared to other tools)
  • 무료이며, 널리 배포된 오픈소스다.
  • 설치와 사용이 간단하다.
  • 실제 프로그램에서 버그를 찾아내며, 개발자가 이를 사용한다.

History Recap

• SAGE는 “smart” 하지만, Microsoft 외부로 릴리즈되지 않았다.
  • 지능적인 프로그램 경로 탐색
• AFL은 “dumb” 하지만, 사용하기 쉽고 버그를 찾는다.
  • “if(input == 0xbadf00d)” 를 해결하기 위해 2^32번 브루트 포스를 수행할 것이다.

Tip of the Spear

스마트 퍼징에서 더 복잡한 버그 자동 탐지 시스템으로의 변화를 살펴보자.

DARPA Cyber Grand Challenge

“Cyber Grand Challenge (CGC)”는 Capture-the-Flag 스타일의 사이버 보안 대회로, 취약점 자동 탐지를 위한 고성능 컴퓨터 제작을 목적으로 한다.

• 팀들은 “Cyber Reasoning Systems” (CRS)를 제작한다.
• CRS에게는 “CBs” 가 주어진다. (aka Pwnables)
• CRS는 “Proof of Vulnerability” (POV) 를 찾는다.
• CRS는 CBs의 취약점을 수정한다.
• CRS는 복잡한 채점 알고리즘에 의해 순위가 매겨진다.

Overlapping Approaches

공개된 모든 전략은 동일한 구성 요소의 조합이었다.

• 퍼징 (Fuzzing)
• 심볼릭 실행 (Symbolic Execution)
• 기타 프로그램 분석 (Other program analyses (alias analysis, reachability, input dependence))
• 해결해야 할 우선 순위 체계 (Prioritization scheme for which problems to solve)
• 상태 제거 체계 (State pruning scheme)
• 리소스 제어 및 할당 (Resource control and allocation)

예상과는 달리 결과에서 큰 차이는 없었다. 1위와 7위의 스코어 차이는 크지 않았다.

Subtle Subproblems

우리는 현재 적용 가능한 기술의 한계가 무엇인지 알고 있다. 이러한 문제를 해결하고 진보해야 한다.

이러한 문제들을 해결한다면, 박사 학위 논문을 채울 수 있을 것이다:

• 초기 입력을 선택하고, 뮤테이션 범위를 선정하기 위한 효율적인 방법은 무엇일까?
• 다음으로 탐색을 실행할 심볼릭 상태(symbolic state)는 무엇이어야 할까? 실제 프로그램은 매우 많은 상태를 가진다.
• 여러 프로그램 분석을 하나로 결합할 수 있을까? 컴퓨터 프로그램을 일관성 있게 표현하고, 이러한 표현에 대해 논할 수 있을까?

Our Solution: “Analysis Booting”

• 기존 분석 도구들을 어떻게 결합할까?

  • 보편적 지식: 입력(input)!
  • 하나의 도구로 생성된 입력을 다른 도구들에 전달

• 어떤 입력이 좋을까?

  • “AAA…” vs. “\x7fELF…”
  • MinSet: 최대 커버리지 대비 최소 집합
  • 새로운 분기 커버리지를 생성하는 입력만을 유지

Sendmail “crackaddr” Bug(CVE-2002-1337 )

“crackaddr” 버그는 Mark Dowd에 의해 2003년에 발견되었으며, Sendmail의 이메일 주소 파싱 함수에서 버퍼 오버플로우가 발생하는 버그다. 상태 머신을 사용하는 파싱 루프로 구성되어 있다. (~500LOC)
2011년, Thomas Dullien은 정적 분석기(static analyzer)로 찾아내기 어려운 작은 버전의 예제를 추출하여 바운티를 내걸었다. (~50LOC)

• Symbolic Execution
  • 루프로 인한 경로 폭발(path explosion) 발생
• Model checking
  • 루프 불변성(loop invariant) 추론 불가능
  • 루프 불변성에 대한 수동 사양(manual specification) 필요
• Abstract Interpretation
  • The over-approximation
  • 상태의 조인(join)과 확대(widening)는 너무 많은 부정확성을 초래
  • 루프 내부의 상태에 대한 파싱 자동화는 분리 불가능

상태 머신을 통과하는 단일 경로만이 서버를 점유한다. 결국 가능한 입력은 10^65535이며, 탐색 공간이 숨겨진 셈이다.

Let’s Validate Email Addresses!

Email 주소를 검증하는 간단한 작업은 괄호와 꺽쇠를 카운팅하는 상태 시스템을 사용하는 것이다.

“(“ 에서는 복사 버퍼에 대한 포인터를 감소시키지 않는다. 이 프로그램에 인코딩된 많은 양의 상태에서 이를 활용할 수 있는 하나의 입력이 있지만, 이를 찾는 것은 매우 어렵다. 우리는 이제 이를 발견할 수 있으며, 이미 여러 시스템이 이를 찾을 수 있다.

p.s. “crackaddr”를 자동 탐지하는 방법에 대해서는 나중에 좀 더 자세히 다뤄봐야겠다.

CGC Upsides

모든 자동화된 시스템들은 실제 버그를 발견했다.
이러한 버그들 중 자동화된 분석기로는 찾기 불가능하다고 생각되던 것들도 포함되어 있다.
CGC Challenge는 이제 버그 찾기 시스템의 효율성을 입증하는 표준 방법이다.
발견된 버그 중 일부는 베테랑 보안 전문가들도 알지 못했던 것들이다.

Spotlight: DARPA Challenge Sets

• 247 C&C++ network services

  • 메일 서버, ftp 서버 등을 구현한다.
  • 실제 RFC는 허용되지 않으며, 모두 커스텀 프로토콜을 가진다.

• Each challenge comes with:

  • 1개 이상의 exploitable 또는 크래시 취약점
  • CWE를 포함한 취약점에 대한 설명
  • 높은 코드 커버리지를 가진 입력 생성기(input generators)
  • 1개 이상의 취약점 확인 트리거(Proof of Vulnerability triggers)
  • ifdefs 컴파일 타임에 보호되는 패치

참고: https://blog.trailofbits.com/2016/08/01/your-tool-works-better-than-mine-prove-it/

CGC Downsides

대부분의 팀들은 전문적인 작업이 필요한 시스템을 구축했다.
사용성의 문제는 CGC scoring이나 규칙에 의해 해결되지 않았다.

대부분의 팀들은 DARPA의 연구 OS를 목적으로 만들어졌다: DECREE.
6개의 시스템 콜만이 존재하며, 파일(files), 쓰레드(threads), 시그널(signals)이 없다.

CGC 콘테스트는 버그 헌팅과 분석에서 많은 혼란이 있었다: 패치 자동화, 네트워크 장비, 리소스 제약 등.

Section Recap

CGC는 자동화 분석 분야에 많은 도움을 주었고, 적시에 이루어졌다.
이제 자동 분석이 가능하며, 매우 효과적이라는 것이 명백하다.
이미 몇 개의 프로토타입 시스템이 존재하며, 이들 중 몇몇은 오픈소스다.
CGC에서 생성된 과제는 버그 탐지 자동화 도구를 비교하기 위한 표준 벤치마크를 제공한다. 버그 탐지 도구의 비교가 가능하다.

Where We Go From Here

Going Mainstream

Microsoft와 Google은 공개 프로그램 분석 서비스를 진행중이다.

• Microsft: https://www.microsoft.com/en-us/springfield/
• Google: https://github.com/google/oss-fuzz

Apple은 곧 시작할 것으로 보인다.

• iOS 10용 비트코드 컴파일은 첫 단계다.
• 재능이 있다: LLVM developers
• 비즈니스 사례가 있다.

참고 : https://github.com/google/fuzzer-test-suite

Research Roadblocks

• Comparison and Effectiveness

  • 이러한 도구들의 동작과 어떻게 비교되는지를 보여주기 위한 현실적인 벤치마크 (SV-comp, but for bug finding)

• The bugs are getting harder

  • 진짜 좋은 분석 도구들은 웹 브라우저를 분석하지 않는다.
  • .. 하지만 할 필요가 없다: 만약 우리가 모든 이미지 및 PDF 라이브러리를 수정했다고 상상해보자.

• Build interoperable tools!

  • 연구를 재사용하는 것은 매우 어렵다. 모든 것을 처음부터 다시 작성해야 한다.
  • LLVM 모델을 채택하자: 도구는 interchange format을 통해 이야기해야한다.

Conclusion

Start Today

Google OSS Fuzz: https://github.com/google/oss-fuzz
Microsoft’s Project Springfield: https://www.microsoft.com/en-us/springfield/
LLVM’s libFuzzer: http://llvm.org/docs/LibFuzzer.html

Play with the open sourced CGC tools:

• https://github.com/trailofbits/grr
• https://github.com/trailofbits/mcsema
• https://github.com/trailofbits/cb-multios
• https://github.com/cybergrandchallenge

---

Bitcode Possibilities

LLVM bitcode는 프로그램 분석을 매우 쉽게 해준다.
Apple은 이제 iOS 앱을 비트코드로 컴파일해야 한다.

• Imagine the following future:
  • 모든 앱의 버그, 백도어, API 오용이 자동으로 분석된다.
  • Apple은 자신들의 앱을 안전하고, 확실하게 마켓에 내놓을 수 있다. 또는 기준을 통과할 때까지 다시 재출하도록 한다.
  • 모든 경쟁사들도 이러한 기능을 충족시켜야 한다.

프로그램 분석에 자본이 투자되고, 우리 모두 혜택을 받는다.

Developer Roadblocks

개발자가 받아들이는 것이 중요하다. 도구는 사람들이 실행할 경우에만 동작한다!
우리(분석 도구 개발자)는 개발자들에게 우리의 도구가 삶을 편하게 해준다는 것을 보여주어야 한다.

• Mindshare and enthusiasm
  • 보안에 집중하는 고객들은 자동화 도구를 신뢰하지 않는다.
• Usability
  • 일반적인 프로그램 분석 도구는 git 보다 못한다.

AFL은 이러한 두 가지 문제를 해결하는 것을 보여주었다. Usability으로 시작하고, Mindshare는 따라온다.

Funding Roadblocks

---

Reference

Original fuzzing project assignment from UW-Madison (1988)
http://pages.cs.wisc.edu/~bart/fuzz/CS736-Projects-f1988.pdf

PROTOS – systematic approach to eliminate software vulnerabilities (2002)
https://www.ee.oulu.fi/roles/ouspg/PROTOS_MSR2002-protos

The Advantages of Block-Based Protocol Analysis for Security Testing (2002)
http://www.immunitysec.com/downloads/advantages_of_block_based_analysis.html

DART: Directed Automated Random Testing (2005)
https://wkr.io/public/ref/godefroid2005dart.pdf

EXE: Automatically Generating Inputs of Death (2006)
https://web.stanford.edu/~engler/exe-ccs-06.pdf

EXE: 10 years later (2016)
https://ccadar.blogspot.com/2016/11/exe-10-years-later.html

Automated Whitebox Fuzz Testing (2008)
https://patricegodefroid.github.io/public_psfiles/ndss2008.pdf

American Fuzzy Lop (AFL)
http://lcamtuf.coredump.cx/afl/

DARPA Cyber Grand Challenge Competitor Portal (2013)
http://archive.darpa.mil/CyberGrandChallenge_CompetitorSite/

Exploitation and state machines (2011)
http://archives.scovetta.com/pub/conferences/infiltrate_2011/Fundamentals_of_exploitation_revisited.pdf

Your tool works better than mine? Prove it. (2016)
https://blog.trailofbits.com/2016/08/01/your-tool-works-better-than-mine-prove-it/

Microsoft Springfield (2016)
https://www.microsoft.com/en-us/springfield/

Google OSS-Fuzz (2016)
https://github.com/google/oss-fuzz

LLVM libFuzzer
http://llvm.org/docs/LibFuzzer.html

GRR – High-throughput fuzzer and emulator of DECREE binaries
https://github.com/trailofbits/grr

Manticore – A Python symbolic execution platform
https://github.com/trailofbits/manticore

McSema – x86 to machine code translation framework
https://github.com/trailofbits/mcsema

DARPA Challenge Sets for Linux, macOS, and Windows
https://github.com/trailofbits/cb-multios

Trail of Bits publications about the Cyber Grand Challenge
https://blog.trailofbits.com/category/cyber-grand-challenge/