Introduction
The Problem
보안 패치는 일반적으로 보안 취약점을 수정하기 위한 것이다. 그리고 문제를 해결하고 컴퓨터와 end user를 위험으로부터 보호하기 위한 것이다. 하지만 패치를 릴리즈하는 것이 새로운 위협을 부과하지는 않는가? 우리는 이 위협을 "1-day exploit"이라고 한다. 패치 릴리즈 후 몇 분 만에 바이너리 diffing 기술을 사용하여 보안 패치로 수정한 취약점을 식별할 수 있다. 이는 아이러니한 상황이지만 요즘 실제로 발생하고 있다.
이 바이너리 diffing 기술은 특히 Microsoft의 바이너리에 유용하다. 다른 vendor와 달리 정기적으로 패치를 릴리즈하고 패치된 취약점은 바이너리의 작은 영역에 상대적으로 집중되어 있다. 이러한 사실 덕분에 patch analyzer는 바이너리의 패치된 영역을 더 가시적이고 분명하게 분석할 수 있다.
우리는 이미 2006년에 "eEye Binary Diffing Suite"를 개발했으며 보안 연구원이 취약점을 식별하는 데 널리 사용하고 있다. 무료 오픈 소스이며 1-day 취약점 헌팅 목적으로 사용하기에 충분히 강력하다. 따라서 사실상 공격자는 방금 패치된 unknown 취약점을 식별하는 데에 필요한 모든 도구와 대상에 액세스할 수 있다. 공격자는 사용자나 기업이 패치를 적용하는 동안 공격을 시작할 수 있다. 패치를 적용하는 프로세스는 일반적으로 몇 분에서 며칠이 거린다.
지난 몇 년 동안 우리가 관찰한 바에 따르면 모든 중요한 보안 패치는 수동 또는 도구를 사용하여 자동으로 바이너리 diffing 되었다. 때때로 연구원들은 패치 분석을 단 20-30분 만에 완료하기도 했다. 겨우 하루 만에 취약점을 식별하고 exploit 할 수 있다. 그리고 바이너리 diffing은 이제 공격자에게 너무 쉽고 저렴해졌다. 패치 적용 기간 동안 end user는 1-day 공격에 더 취약해지고 표적이 된다.
The Answer
따라서 이제 vendor는 소비자가 패치를 적용하는 데 더 많은 시간을 벌 수 있도록 이러한 1-day exploit을 더 어렵고 시간 소모적으로 만드는 것이 중요해졌다. 극심한 코드 난독화를 사용하는 것이 Microsoft 제품의 옵션은 아니지만 안정성과 사용성을 포기하지 않고 바이너리 diffing 프로세스를 무력화할 수 있는 몇 가지 전략과 기술을 따를 수 있다. 바이너리 diffing을 더 어렵게 만드는 방법과 전략을 보여줄 것이다. 그리고 바이너리가 특히 혼동되는 방식으로 바이너리를 난독화하는 사내 도구를 보여줄 것이다. 우리는 이 과정을 anti-binary diff라고 부른다.
Binary Diffing
The History
10년 전 Bmat paper[BMAT]가 소개한 이후로 바이너리 diffing은 이제 매우 일반적이고 저렴한 기술이다. "bindiff"와 같은 값비싼 상용 도구 외에도 패치 파일에서 정확한 패치 지점을 식별하는 데 사용할 수 있는 무료 또는 오픈 소스 도구가 이미 2-3개 있다. 본 섹션에서 바이너리 diffing 이론과 도구의 간략한 역사를 소개하겠다.
BMAT(1999)
이는 symbolic name matching에 크게 의존한다. 주로 심볼에 액세스할 수 있는 Microsoft의 바이너리에 사용되었다. 이름 기반 매칭은 matching procedure나 matching function을 식별한 후 각 procedure 내 블록에 대해 해시 기반 비교를 수행한다. instruction에서 계산된 64비트 해시 값을 사용하며, checksum은 순서에 의존적이다. 해싱은 instruction byte에서 생성된다. opcode 및 operand를 사용하는 multi level 추상화가 있다.
해당 논문은 보안 패치 분석이 아닌 profile propagation의 transfer에 주로 초점을 맞추고 있다. 해당 논문의 장점은 블록 매칭에 checksum을 사용하는 것을 제안했다는 점이다. 코드 최적화를 통해 코드 변경 없이 동일한 블록을 변경할 수 있는 경우가 있다. 그러나 일반적으로 vendor는 최적화 수준을 변경하지 않으며 basic block의 레지스터 및 instruction 순서는 일반적으로 동일하게 유지된다. 따라서 평상시에는 전체 instruction text 대신 basic block을 checksum하고 비교하는 것만으로도 충분하다. 또한 basic block에 대해 5가지 레벨의 checksum 방식을 보여주었다. 그들은 이러한 레벨을 "matching fuzziness levels"이라고 부른다. 레벨이 감소할수록 해시가 계산에 사용할 정보가 점점 더 많아진다. 레벨 0은 기본적으로 레지스터 할당과 block address operand and operands와 opcode를포함한 basic block의 모든 정보를 가지고 있다. 레벨 5에는 opcode 정보만 있다.
또한 해당 논문에서는 CFG 기반 basic block 매칭을 방법을 사용한다. 이 매칭 방법은 실제로 바이너리 diffing에서 기본적인 방법이다.
Automated Reverse Engineering(2004)
Halvar는 Blackhat 2004에서 리버스 엔지니어링 기술[ARE]에 대해 발표했다. 그리고 바이너리 diffing을 위해 함수의 fingerprint를 사용할 것을 제안했다. 기본적으로 동일한 아이디어가 그의 다음 논문과 bindiff 도구에 사용된다. 아이디어는 독특하고 간단하다. node, edge, call count를 특성으로 사용하여 함수 시그니처를 구성한다. 그리고 바이너리 간에 비교한다. 해당 논문에서는 함수 CG(call graph) 간의 isomorphic comparison를 제안한다.
Comparing binaries with graph isomorphism(2004)
Todd Sabin은 isomorphic analysis와 두 개의 바이너리 매칭[TODD]을 제안했다. instruction 그래프의 동형 매칭을 기반으로 한다. 그것은 전체 구조를 diffing하기 위해 분할 정복 전략을 채택했다. 흥미로운 점은 basic block이 아닌 instruction을 비교한다는 점이다. 그러나 instruction 비교는 basic block 매칭과 함수 매칭으로 merge된다. 그는 바이너리 diffing 성능이 수용 가능하고 사용 가능하다고 주장했다. 그러나 POC는 출시되지 않았다.
Structural Comparison of Executable Objects(2004)
Blackhat 2004에 발표된 Halvar의 "Automated Reverse Engineering(2004)"[ARE]에 대한 향상된 버전이 발표되었다[SCEO].
Graph-based comparison of Executable Objects(2005)
Halvar는 이전 논문 "Structural Comparison of Executable Objects(2004)"을 발전시켰다. 기본 아이디어는 동일하다.
문제는 알고리즘이 바이너리의 CFG generation에 크게 의존한다는 것이다. 논문에서 말했듯이 현대 바이너리에서 CFG와 CG를 추출하는 것은 간단한 일이 아니다. 바이너리 자체의 완전한 CFG 분석은 어려운 작업이며 CFG의 불일치는 전체 바이너리의 주요 분석 실패를 초래할 수 있다.
CFG 인식 실패를 무시할 수 있지만 이는 많은 false negative를 의미한다. 그리고 중요한 부분을 놓치는 경우가 있다. 또한 이 알고리즘은 상수 값을 사용하거나 레지스터 변경과 같은 구조적 변경을 일으키지 않는 패치를 인식할 수 없다.
The Tools
현재까지 존재하는 모든 메이저 바이너리 diffing 도구(상업 도구나 무료 도구)를 발표할 것이다. 또한 그들의 알고리즘을 비교하고 리얼 월드에서의 효과를 보여줄 것이다.
Sabre Security's bindiff(2004)
Halvar는 그의 그래프 기반 fingerprint 이론을 기반으로 상업 바이너리 도구를 만들었다.
IDACompare(2005)
도구의 설명을 보면 시그니처 스캔을 기반으로 한 것처럼 보인다. 우리는 도구를 테스트하지 않았지만 주로 악성파일 분석 데이터 porting을 대상으로 한다. 또한 mdb를 사용하고 있으며 페이지에는 약 500k 파일 크기용으로 설계되었다고 나와 있다. 일반 패치 diffing의 경우 바이너리 파일은 1MB 이상 10 ~ 20 MB가 될 수 있다.
eEye Binary Diffing Suite(2006)
우리는 2006년 여름에 eEeye에 오픈 소스 바이너리 diffing suite를 개발했다. 이는 Microsoft의 Patch Tuesday 패치 분석을 위해 내부적으로 사용되었다. 그 당시 Microsoft는 vendor에 패치 정보를 제공하지 않았으며, 패치 분석은 그들이 공개하지 않는 일부 비밀 정보를 얻을 수 있는 유일한 방법이었다.
"DarunGrim"은 포함된 도구 중 하나이며 주요 바이너리 diffing 분석을 수행한다. 이 도구는 sqlite 데이터베이스를 사용하여 차분 분석 결과를 저장한다. 이 도구에서 사용하는 주요 알고리즘은 DarunGrim2에서도 기본적으로 사용된다. 파이썬으로 작성했기 때문에 분석 대상이 10MB 정도보다 클 때 성능이 떨어졌다. 이는 DarunGrim2에서 Python 대신 C++를 사용하여 해결했다.
Patchdiff2(2008)
도구 설명에 따르면 이 도구는 보안 패치 또는 hotfix 분석에 특화되어 제작되었다고 한다. 유사한 함수 찾기 또는 악성코드 유사성 연구에는 적합하지 않은 도구다. Tenable Security에서 무료로 배포하고 있다. 문서에 따르면 signaturing을 위해 그래프 호출의 checksum을 사용하는 것처럼 보이므로 Halvar와 유사한 체계를 가지고 있는 것 같다.
DarunGrim2
eEye Binary Diffing Suite의 개선된 버전이다. 가장 큰 차이점은 Python 대신 C++를 사용한다는 것이다. 그 외에도 DarunGrim의 이전 버전에 비해 많은 개선 사항이 도입되었다.
DarunGrim2
Algorithms
우리는 알려진 모든 바이너리 diffing 알고리즘과 실무에서 사용 가능한 전략을 제시할 것이다. 우리가 수집한 실험 데이터를 diffing 도구를 이용해 알고리즘을 설명할 것이다. 각 알고리즘의 효율성을 보여주기 위해 몇 가지 통계적 방법이 사용된다. 단순하게 보이는 알고리즘은 심각한 취약점을 식별하는 데 놀라울 정도로 강력할 수 있다. engine은 fingerprint 해싱 방식을 기반으로 procedure를 빠르고 안정적으로 매칭한다. 이전까지의 바이너리 diffing 분석은 주로 그래프 구조 분석과 그래프 동형에 집중되었다. 하지만 두 그래프를 집중적으로 비교해야 하고, 디스어셈블러의 CFG 분석 능력에 의존하는 단점도 있다. CFG가 완료되지 않은 경우 전체 procedure는 unmatched 상태로 유지된다. 간접 호출과 같은 일부 패턴은 동형 분석을 사용하여 분석할 수 없다. 이름 매칭은 procedure 매칭에도 널리 사용되지만, 심벌을 사용할 수 없는 경우 사용할 수 있는 선택지가 아니다.
fingerprint hashing은 이러한 한계를 극복하고 분석 결과를 획기적으로 향상시키는 방법이며, 고성능이라는 장점도 있다. fingerprint 해싱을 구현하는 방법을 제시하고 실제 바이너리 diffing 분석 예제를 보여주겠다.
그러나 DarunGrim2에서 사용되는 알고리즘은 fingerprint 해싱만이 아니라 fingerprint 매칭을 기반으로 함수를 매칭하는 알고리즘도 있다. 또한 DarunGrim2는 전통적인 동형 알고리즘과 이름 매칭을 사용한다.
Symbolic Names Matching
DarunGrim2는 다른 바이너리 diffing 도구와 마찬가지로 symbolic names matching을 사용한다. 이는 바이너리 매칭 절차의 기본적인 시작점이다. 심볼릭 이름은 exported name 또는 vendor가 제공한 심볼에서 검색한 이름일 수 있다. 일반적으로 심볼 파일은 대중에게 제공되지 않지만 Microsoft는 패치가 나오는 즉시 심볼 파일을 누구에게나 제공할 만큼 친절하다. 따라서 바이너리 diffing 프로세스와 취약점의 실제 추적에 많은 도움이 된다.
Fingerprint Hash Map
What is a fingerprint?
우리는 DarunGrim2의 주요 알고리즘으로 fingerprint hashing 방식을 제시하고 있다. 이 방법은 매우 간단하다. 또한 바이너리에 대한 집중적인 분석 없이도 구현할 수 있다. fingerprint hashing은 instruction sequence를 추상화하는 방법이라는 의미로 쓰인다.
일반적으로 fingerprint는 컴퓨터 과학에서 여러 의미를 가질 수 있다. 본 논문에서 fingerprint는 basic block을 표현하는 data byte로 사용된다. 모든 basic block에 대해 DarunGrim2는 code byte feature를 추출하고 이를 해시 테이블의 key로 사용한다. 우리는 이를 block의 fingerprint라고 부른다. 크기는 가변적일 수 있으며 실제 instruction byte 크기의 합에 상대적일 수 있다. fingerprint를 만드는 방법은 여러 가지가 있을 수 있다.
fingerprint matching은 basic block을 효율적으로 매칭하는 방법이다. basic block은 diff 분석의 기본 요소이다. 이는 하나 이상의 code referencing block이 있는 basic block이다. 해시 테이블을 작성하는 데에 O(n)이 걸린다. DarunGrim2는 원본 바이너리와 패치된 바이너리에 대해 두 개의 fingerprint 해시 테이블을 구축한다. 원본 바이너리 fingerprint의 고유한 fingerprint 각각에 대해 DarunGrim2는 패치된 바이너리 fingerprint 해시 테이블에 매칭되는 entry가 있는지 확인한다. 이 절차는 해시 테이블을 검색하는 데에 O(1)이 걸리므로 O(n)이 걸린다.
flirt-like 전통적인 함수 레벨 fingerprint과 달리, DarunGrim2는 추상화된 형태의 fingerprint byte를 basic block의 hash data로 사용한다. 따라서 함수의 basic block 중 일부가 수정되더라도 다른 매칭 basic block이 함수 매칭을 지원해준다. 생성된 엄청난 수의 fingerprint 해시를 더 빠르게 매칭하기 위해 고유한 모든 fingerprint 문자열을 해시 테이블에 넣고 이를 fingerprint matching에 사용한다. basic block에 대한 fingerprint을 생성하는 방법에는 여러 가지가 있을 수 있다. 그리고 fingerprint 생성 방식을 스위칭하면 매칭 과정에서 다른 동작을 보인다.
Generating fingerprint for a basic block
basic block의 fingerprint를 생성하는 가장 간단한 방법은 opcode와 operand를 사용하는 것이다. 이 방법에서는 basic block의 fingerprint 생성이 가장 중요한 부분이므로 컴파일러 및 링크 옵션에 따라 fingerprint 생성 시 고려해야 할 사항이 거의 없다. 소스 코드 수정에 따라 변경되는 경향이 있기 때문에 메모리 또는 immediate type operand를 무시하도록 결정할 수 있다. 레지스터 difference를 무시하고 하나의 representation으로 만들 수 있다. fingerprint 생성 방법에는 여러 가지가 있을 수 있다.
Using IDA
구현은 바이너리 분석을 위해 IDA를 사용한다. 따라서 fingerprint 생성은 IDA의 디스어셈블리 표현에 따라 달라진다. 그리고 IDA는 이 정보를 추출할 수 있는 좋은 structure를 제공하고 있다. DarunGrim2 플러그인은 insn_t 구조를 사용하여 instruction에 대한 정보를 retrieve한다.
Overcoming Order Dependency
fingerprint의 단순 순차적인 추출의 단점은 순서에 의존한다는 것이다. 실제로 이 문제는 instruction 순서에 의존하는 모든 알고리즘에 공통적인 문제다. 따라서 이 문제를 해결하기 위해 시그니처를 생성하기 전에 instruction ordering normalization를 수행하는 옵션도 있다. 이것은 서로 의존적인 instruction을 선택하여 수행된다. 그리고 instruction byte 오름차순으로 정렬한다. dependent instructions sequence는 어쨌든 순서를 유지해야 한다. 이 instruction ordering normalization은 instruction reordering을 사용하여 aggressive 최적화를 수행하는 컴파일러로 빌드된 바이너리에 특히 중요하다.
Reducing Hash Collision
short basic block이 있을 수 있으며 하나의 바이너리에 중복되는 경향이 있다. 즉, 바이너리에서 고유하지 않은 fingerprint가 있을 수 있다. 이것은 해시 테이블에서 사용될 때 해시 충돌을 일으킨다. 기본적으로 우리는 비교를 위해 충돌이 있는 항목을 무시하고, 사용하지 않는다. 그러나 충돌률을 낮추는 더 좋은 방법이 있다. one blocks fingerprint를 fingerprint CFG에서 연결된(:connected) 다음 블록과 연결(:associating)함으로써 충돌 블록을 고유하게 만들 가능성이 있다. 그런 식으로 여러 연결된 블록에 fingerprint 해싱을 사용하고 충돌 수를 줄일 수 있다.
Determining functions matching pair
해시 테이블을 traverse하고 블록을 매칭한 후, 원본 바이너리의 모든 procedure에 대해 패치된 바이너리의 procedure와 매칭되는 수를 계산한다. 한 procedure에 대해 '패치된 바이너리의 다른 procedur들과 매칭되는 basic block들'이 있는 경우 그 중 하나를 선택해야 한다. 이를 수행하기 위해 간단한 방법을 사용한다. 매칭되는 각 페어의 entry 수를 계산하고 가장 높은 수의 매칭 entry를 선택한다. 가장 높은 횟수가 같은 entry가 여러 개 있는 경우 그 중 하나를 무작위로 선택해야 한다.
따라서 각 함수에 대한 매칭 횟수를 비교하여 매칭 횟수가 가장 큰 함수 매칭 쌍을 선택하여 matching function을 결정한다. matching function이 결정되면, non-matching function에서 matching basic block이 있는 non-compliant matching pair는 모두 취소(:revoke)된다.
따라서 matching function에 대한 결정 프로세스는 주로 fingerprint matching에 의존한다. 그리고 실제 패치의 경우 basic block fingerprinting이 우수한 성능과 퀄리티를 보임을 발견했다.
Matching blocks inside function
matching function이 결정되면 각 함수 내부의 블록은 일종의 locality을 갖게 된다. 그래서 다시 각 함수 내부의 basic block에 대한 fingerprint 해시 테이블을 구성하고, 이에 대한 fingerprint matching을 수행할 수 있다. 이를 "fingerprint match inside function"라고 한다. 이 경우 node number는 상대적으로 작다. 충돌 확률도 이전에 수행된 global fingerprint matching에 비해 매우 낮다.
How does it look like?
다음은 데이터베이스 내부의 fingerprint representation의 예시이다.
Structure Based Analysis
Structure based analysis: basic block isomorphism
matching function을 결정하고 fingerprinting match inside function을 마친 후 structure based analysis를 수행한다. 이는 Halvar의 방법과는 다른다. 우리의 방법은 단지 절차적이며 분할 정복의 철학을 가지고 있다. 우리는 basic block을 그래프 노드로 사용하기 때문에 Todd의 isomorphic 알고리즘과 다르다. 내가 아는 한, 이 매칭 알고리즘은 BMAT 도구[BMAT]에 제시된 것과 유사하다. 이는 known matched node에서 children's nodes를 매칭시키려고 시도한다.
Control flow Inversion
이 과정에서 control flow inversion을 고려해야 한다. 제어 흐름 반전 문제는 Todd의 문서[TODD]에서 이미 알려져 있다. DarunGrim2는 negative comparison type jmp(jnz, jle 등)가 발생하면 CFG를 조정한다.
다음은 code inversion 제거 프로세스를 보여주는 C 스타일 pseudo code다.
Calculating Match Rate
procedural structural matching을 수행할 때 두 개의 basic block이 같거나 유사한지 판단해야 한다. 이 작업을 수행하기 위한 수단으로 fingerprint를 사용한다. fingerprint는 실제 코드 instruction에서 추출되기 때문에 basic block의 실제 구현을 보여주고 분석을 위해 추상화 및 정규화되었다. fingerprint는 fingerprint 매칭이 수행될 때 메모리에 바이너리 byte sequence로 저장되지만 hex ascii 형식 표현으로 쉽게 변환될 수 있다. 변환된 형태의 ASCII 문자열로 우리는 잘 알려진 문자열 매칭 알고리즘을 사용하여 basic block의 유사성을 계산한다. 이 부분은 약간의 시간이 소요되며 실제 instruction byte를 사용하거나 basic block의 디스어셈블리 표현을 사용하면 false match rate이 더 높아진다.
따라서 이 모든 프로세스가 완료된 후 매칭 프로세스의 멤버가 아닌 unmatched code block으로 전체 매칭 프로세스를 다시 반복한다. 어떤 방법으로든 매칭되는 entry가 생성되지 않을 때까지 이 프로세스를 반복한다.
리얼 월드에서, 특히 Microsoft 패치 분석과 같은 상황에서 fingerprint matching 및 procedural structural matching은 바이너리의 패치된 부분을 식별하는 데에 충분하다.
Real Life Issues
각 vendor가 다른 컴파일러와 최적화 방법을 사용하기 때문에 실제 바이너리를 구별하는 데 몇 가지 문제가 있다.
Split Blocks
최적화의 일환으로 여러 위치에 split block이 있다. 다음과 같이 split block을 정의할 수 있다:
- "자식이 하나 있는 block 그리고 block의 자식은 CFG에 부모가 하나만 있는 경우"
split block은 CFG를 손상시키고 매칭 프로세스를 불완전하게 만드는 경향이 있다. 다음은 예시 상황이다. 왼쪽 창의 757AC02B 블록과 오른쪽 창의 7CB411B5 + 7CB411BA 블록이 동일하다. 그러나 오른쪽 창의 블록은 분할되어 모든 하위 블록이 빨간색으로 표시되므로 일치하더라도 일치하는 블록으로 인식되지 않는다.
DarunGrim2는 이러한 split block을 인식하여 하나의 블록으로 병합한다. 이 병합 프로세스를 적용한 후 동일한 코드 블록에 대한 바이너리 매칭 결과는 다음과 같다.
모든 unmatched block이 이제는 매칭 된 것을 볼 수 있다.
Hot Patching
Microsoft의 바이너리에는 실제 함수가 시작되기 직전에 hot patch instruction이 있는 경우가 있다. 다음은 hot patch preamble이 있는 함수의 예시다.
빨간색 부분은 hot patch instruction이며 일반적으로 hot patch install을 위한 공간을 예약하는 것 외에는 아무 효과가 없는 "mov eax, eax"이다. 이는 race-condition없이 hot patching process를 만들 수 있는 2-byte의 instruction이다.
종종 원본 바이너리에는 없고 패치된 바이너리에는 있다. 그러면 basic block이 수정된 것처럼 보인다. 따라서 DarunGrim2는 모든 hot patch instruction을 무시한다. 함수 시작 시 동일한 레지스터에 대해 "mov" 연산을 수행하는 instruction이 있을 때 DarunGrim2는 basic block fingerprint를 생성할 때 이를 무시한다.
Basic Blocks in Multiple Functions
일반적으로 하나의 basic block은 하나의 함수에 속한다. 그러나 최적화를 위해 하나의 basic block이 여러 함수의 일부가 되는 경우가 있다.
다음은 Windows 커널 디스어셈블리에서 41fbc2의 basic block이다. IDA 디스어셈블러는 "MmCopyToCachedPage" 함수의 일부라고 인식한다.
그러나 custom tool을 사용한 code flow 분석에서, 특정 basic block이 둘 이상의 함수에 속한다는 것을 발견했다.
위의 분석 결과에서 41fbc2(노란색)의 basic block이 "MmUnmapViewInSystemCache", "MmCopyToCachedPage", "MiRemoveMappedPtes" 함수의 일부임을 알 수 있다. 이러한 종류의 basic block에 대한 multiple function ownership은 적절한 바이너리 diffing 프로세스를 방해할 수 있다. IDA의 한계는 하나의 basic block에 대해 하나의 함수 매칭만 지원한다는 것이다. DarunGrim2는 custom CFG analysis를 수행하여 이 문제를 해결하고, basic block이 여러 함수에 속할 수 있도록 한다.
Instruction Reordering
리얼 월드에서 instruction reordering은 많이 일어나지 않는다. 특히 Microsoft의 바이너리에서는 instruction reordering 사례를 많이 보지 못했다. 그러나 ARM 바이너리 diffing 실험 동안 우리는 각 릴리즈에서 많은 instruction reordering이 발생한다는 것을 발견했다. "Illustration 4: ARM 바이너리의 instruction reordering"은 iPhone 2.2 버전과 3.0 버전의 diffing 결과다. 해당 함수는 이름 매칭으로 매치되었지만, 루트 노드는 노란색으로 표시되어 basic block이 다름을 의미한다.
그래서 우리는 두 가지 basic block의 디스어셈블리를 확인했다.
original과 패치된 basic block은 기본적으로 동일하다. 유일한 차이점은 많은 instruction이 swap된 각 instruction의 순서다.
따라서 이 instruction reordering 문제를 해결하기 위해 variable tracing과 sorting 방법을 사용하는 grouping을 사용한다. 각 레지스터 또는 displacement variable의 변경 및 사용 경로를 추적할 수 있다. 예를 들어 "Illustration 5: Part of register, displacement variable and call arguments trace of the patched basic block"는 패치된 바이너리 basic block의 variable trace의 일부를 보여준다. DarunGrim2는 현재 레지스터, displacement variable 및 call argument tracing을 지원한다.
variable tracing을 사용하여 각 instruction 노드를 그룹화할 수 있다. 여러 그룹이 있을 수 있으며 서로 독립적이고, 그룹 간의 instruction 순서는 서로 영향을 미치지 않는다. 각 그룹에서 해시 값을 계산한다. 해시는 instruction 타입과 operand의 타입과 값을 사용한다. immediate value나 메모리 참조를 의도적으로 무시한다. 이는 빌드에서 무작위로 나타나는 경향이 있으며 적절한 계산을 방해한다. 해시 값이 계산되면 각 블록을 정렬하고 정렬된 순서로 나열한다.
"Table 2: After Grouping And Sorting"는 그룹화 및 정렬 결과를 보여준다. immediate value와 메모리 참조 값을 제외하고 동일한 instruction sequence를 보여준다. 이 instruction reordering 프로세스는 sequential fingerprint를 수집하는 원래 방법보다 더 많은 CPU를 소모한다. 따라서 이 기능은 필요할 때 선택적으로 사용할 수 있다.
Examples
실제 Microsoft 패치의 바이너리 diff 결과를 보여주고 패치 포인트 식별의 효율성을 보여주겠다. 3-4개의 중요 등급 패치를 예로 사용하겠다. 중요하고 찾기 어려운 취약점을 패치에서 찾아내기 어려울 필요는 없다. 이를 보여주기 위해 DarunGrim2를 사용할 것이다.
Microsoft's Binaries
Why are Microsoft's binaries easy targets?
매월 두 번째 화요일에 보안 패치를 릴리즈한다. 따라서 패치에는 보안 수정 코드만 포함되는 경향이 있다. 일반적으로 기능 향상이 없거나 다른 유형의 패치가 패치에 포함되어 있다. 기능 향상은 월간 패치가 아닌 서비스 팩에 있다. 따라서 바이너리 diffing으로 순수한 보안 관련 패치 parts를 얻을 수 있다.
따라서 수정된 코드를 이애하는 데에 걸리는 시간을 단축할 수 있다. 또한 마이크로소프트는 symbol을 제공한다. 일반적으로 시스템 dll, 드라이버, 커널 이미지에 대한 심볼을 제공한다. IIS, Active Directory, Microsoft Office와 같은 비핵심 OS 제품에 대한 심볼은 제공하지 않는다. 그러나 많은 치명적인 취약점이 시스템 DLL, 드라이버, 커널에서 발견되며, 공격자는 Microsoft가 제공하는 심볼을 사용하여 바이너리 diffing에 대한 확신을 높일 수 있다. 또한 수정된 코드를 이해하는 데 시간을 많이 절약할 수 있다.
마이크로소프트는 어떤 코드 난독화도 하지 않는다. 코드 최적화를 제외하고는 일반적으로 코드 난독화를 수행하지 않는다 실제로 코드 난독화를 수행하면 많은 문제가 발생한다. 예를 들어, 다른 제품과 충돌할 수 있으며 디버깅 프로세스를 매우 어렵게 만들 수도 있다. 그래서 shipping products에 코드 난독화 기술을 사용할 수 없을 것이라고 생각한다.
이것은 바이너리 diffing 과정을 보다 쉽고 비용면에서 효율적으로 만든다. 패치에서 수정된 코드의 양은 다른 vendor에 비해 상대적으로 적다. 이는 Microsoft가 코드 유지 관리를 잘하고 있음을 의미한다. 바이너리 differ의 관점에서 이는 아주 쉬운 대상이다.
Gathering Binaries
Microsoft의 바이너리를 수집하는 것은 매우 쉽다. 각 패치 페이지를 방문하면 된다. 예를 들어 MS08-067 문제의 경우 http://www.microsoft.com/technet/security/Bulletin/MS08-067.mspx를 방문하여 운영 체제와 일치하는 바이너리를 다운로드할 수 있다. 그런 다음 "/x" 옵션을 사용하여 패키지 내부의 바이너리를 추출할 수 있다. 하드 디스크에서 이전 버전의 바이너리를 찾아 IDA를 열고 파일을 로드하고 diffing을 시작하면 된다. 이 전체 프로세스는 일반적으로 30분 미만이 소요된다.
The infamous MS08-067(which was exploited by Conficker)
MS08-067은 매우 흥미로운 패치다. netapi32.dll 내부의 스택 버퍼 오버플로 문제를 패치하고 있다. 그리고 진짜 문제는 anonymous pipe를 통해 스택 오버플로에 도달할 수 있다는 것이다. 즉, 이 exploit은 자격 증명 없이 원격으로 exploit될 수 있다. 이 취약점은 Conficker worm과 함께 사용되어 네트워크의 모든 시스템을 감염시킨 후 내부 네트워크를 통해 전파된다.
바이너리 diffing의 관점에서 MS08-067은 매우 쉬운 타겟이다. 수정된 블록을 식별하는 데 몇 분 밖에 걸리지 않는다. 그리고 변경된 함수는 두 개다. 게다가 하나는 calling convention의 변경이다. 따라서 변경된 함수는 하나뿐이다.
물론 실제로 취약점이 발생한 원인을 파악하려면 패치된 함수에 대한 더 많은 연구와 분석이 필요하다. 이는 바이너리 diffing art 자체의 범위를 벗어난다. 바이너리 diffing은 패치 분석 과정을 통틀어 시작점이다. 특히 MS08-067 패치의 경우 수정된 코드가 방대하여 일부 데이터를 처리하는 데 큰 실수가 아닐 수 있음을 쉽게 짐작할 수 있다. 더 많은 분석을 통해 실제 취약점이 드러날 것이다.
MS08-063: DarunGrim2 vs bindiff
DarunGrim2로 바이너리 diffing을 하면 다음과 같은 함수가 수정되었음을 알 수 있다. 추가된 흥미로운 basic block을 찾기 위해 하나씩 확인할 수 있다. "Illustration 11: Screenshot from bindiff manual"은 수정된 함수 목록을 보여준다.
"_SrvIssueQueryDirectoryRequest@32"에는 보안 문제를 해결하기 위한 패치가 있다. 함수의 호출 그래프는 다음과 같다.
수정된 original basic block은 다음과 같다.
"Illustration 8: Zoomed out view of the modified function(_SrvIssueQueryDirectoryRequest@32)"에서 아래 빨간색 블록은 추가된 basic block이며 데이터에 대한 anity check를 수행하고 있다.
패치에서 "RtlUlongSub" 함수를 호출하고 결과에 따라 C000000Dh return code를 반환하는 것을 볼 수 있다. 어떤 데이터가 sanity를 검사하는지 더 추적하면 어떤 종류의 취약점을 수정하는지 알 수 있다.
그래서 DarunGrim2는 7개의 수정된 함수를 찾는다. 그리고 각 변경 사항을 살펴보면 대부분이 일종의 sanity check나 의미 있는 변경 사항이 추가되었다.
bindiff의 매뉴얼 페이지를 보면 정확히 동일한 바이너리를 사용하여 바이너리 diffing 예제를 볼 수 있다. 그러나 bindiff help file의 스크린샷에는 3가지 함수 변경 사항만 표시된다.
따라서 Halvar가 그의 논문에서 언급했듯이 node, edge, call count를 사용하는 함수 fingerprint는 일반적으로 false negatve가 거의 없다. 이는 CFG 구조를 변경하지 않고 패치를 수행하는 경우 때때로 중요하다.
다음은 "_SrvIssueQueryDirectoryRequest@32"를 보여주는 bindiff help file의 그래프 스크린샷이다. Primary는 패치된 파일이고 Secondary는 원본 파일이다. 그리고 diffing 결과가 DarunGrim2와 동일한 것을 확인할 수 있다.
따라서 이 diffing 예제는 DarunGrim2 diffing 방식이 bindiff만큼 유용하고 실용적임을 보여준다. 그리고 때로는 더 자세한 diff 분석을 원할 경우 DarunGrim2가 더 나은 결과를 보여줄 수 있다. 그러나 이것이 어떤 도구나 알고리즘이 우월하거나 열등하다는 것을 의미하지는 않는다. 둘 다 장단점이 있으므로 특정 요구 사항에 따라 도구와 알고리즘을 선택해야 한다.
MS09-020: WebDav case
패치를 diffing하면 다음과 같은 함수가 매칭되고, 수정된 것으로 표시된다. 이 문제에서 흥미로운 점은 원본 또는 패치된 바이너리에 미확인 블록이 없다는 것이다. 9개의 basic block만 수정되었다.
따라서 다음 basic block에서 가장 중요한 변경이 발생했다. 다음은 원본 바이너리의 블록을 보여준다.
다음은 패치된 바이너리의 basic block이다.
처음에는 차이가 눈에 띄지 않는다. 그러나 "MultiByteToWideChar" 호출에 대한 두 번째 인자가 변경되었음을 알 수 있다. 원래 바이너리는 다음 어셈블리 sequence를 사용하여 가져온다.
"eax"를 사용하여 일부 산술 연산을 수행하고 결과가 호출의 flag에 사용된다. 그러나 주소 6F069641에서 "FisUTF8Url" 함수에 대한 호출이 TRUE를 반환하면 "esi"와 "[ebp-124h]"가 동일한 값을 갖게 된다. 따라서 플래그는 0이 된다.
MSDN(http://msdn.microsoft.com/en-us/library/dd319072(VS.85).aspx)은 다음과 같이 선언한다:
"FIsUTF8Url"은 완전한 UTF8 인식 루틴이 아니지만 문자열이 UTF8처럼 보이는지 확인하기 위해 heuristic character range check을 수행하고 있다. 문자열이 UTF8처럼 보이지만 여전히 유효하지 않은 UTF8 문자열일 수 있다. 그리고 "MB_ERR_INVALID_CHARS" 플래그를 지정하지 않으면 함수가 오류를 무시하고 문자열을 변환한다.
이 취약점은 특별하다. 그 이유는 fix 결과가 그 어떤 CFG 구조의 변화도 초래하지 않았기 때문이다. 유일한 변경 사항은 블록 내부의 몇 가지 instruction들이다. "bindiff"와 같은 CFG 기반 매칭 도구는 이러한 종류의 패치를 놓칠 가능성이 있다.
Non-MS Binaries
JRE Font Manager Buffer Overflow(Sun Alert 254571)
심볼이 없는 바이너리 diff도 가능하다. Sun Microsystems는 바이너리에 대한 심볼을 제공하지 않는다. 그러나 대상 바이너리의 바이너리 diffing을 사용하면 다음과 같은 결과를 얻을 수 있다.
패치되지 않은 바이너리는 다음과 같다.
패치된 바이너리는 다음과 같다.
IDA에서 더 많은 디스어셈브릴의 parts를 검색했다. 원본 및 패치된 parts는 다음과 같다. 패치된 바이너리에는 빨간색 줄이 추가되었다.
빨간색 부분을 보면 edi 레지스터의 값이 2000000h 이상인지 확인하고 있는 것을 알 수 있다.
orignal check만 ecx(edi+0ah) 값이 2000000h(6D2C4A7C) 이상이다. 추가적인 edi 값 검사는 실제로 integer overflow를 방지한다. 예를 들어 edi가 0xffffffff이면 ecx는 0xffffffff + 0xa = 0x9가 된다. 원본 바이너리에서 ecx는 2000000h보다 작기 때문에 테스트를 통과한다. 그러나 패치된 바이너리에서 주소 6D244B10의 cmp edi, eax는 큰 edi 값을 필터링한다. 이것은 integer overflow를 방지하는 데 도움이 될 수 있다.
따라서 이 부분에서 integer overflow가 발생하고 있음을 알 수 있다. 추가적인 조사를 통해 데이터가 들어오는 위치를 찾을 수 있다. 이는 공격자가 제어할 수 있는 위치여야 한다.
실제로 여기의 원본 권고(iDefense Security Advisory 03.26.09: Sun Java Runtime Environment (JRE) Type 1 Font Parsing Integer Signedness Vulnerability)는 취약점을 다음과 같이 설명한다.
따라서 방금 찾은 패치가 취약점 설명과 일치함을 알 수 있다.
Anti-Binary Diffing
따라서 이제 사용자가 패치를 적용하는 데 더 많은 시간을 할애할 수 있도록 이러한 관행을 더 어렵고 시간이 많이 소요되도록 만드는 것이 중요해졌다. 극심한 코드 난독화를 사용하는 것이 Microsoft 제품의 옵션은 아니지만 안정성과 사용성을 포기하지 않고 바이너리 diffing 프로세스를 defeat할 수 있는 몇 가지 전략과 기술을 따를 수 있다. 바이너리 diffing을 더 어렵게 만드는 방법과 전술을 보여줄 것이다.
바이너리 diffing을 방지하는 효과적인 방법에 대한 몇 가지 아이디어와 정보를 제공하겠다. 우리는 바이너리 diffing 방법을 방어하는 데에 사용할 수 있는 전술과 알고리즘을 보여줄 것이다. 일부는 vendor가 수행하는 관행 및 프로세스와 관련되고 나머지는 완전히 기술적인 것이다.
이러한 종류의 바이너리 diffing 분석을 방지하기 위한 몇 가지 조치를 생각할 수 있다.
Symbol Mangling
procedure에 대한 심볼 이름 변경에 대해 생각해볼 수 있다. 많은 구현은 기본적으로 procedure 및 변수의 심볼 이름에 의존한다. 따라서 원본 바이너리와 패치된 바이너리에 다른 이름을 사용하면 이름 기반 procedure 매칭을 무용지물로 만들 수 있다. BMAT은 실제로 이름 매칭에 크게 의존하며 유사성 기반 이름 매칭도 수행하고 있다. 따라서 heuristic name matching을 피하기 위해 이름을 mangling해야 한다.
Reordering and replacing instructions
일부 바이너리 diffing 도구는 basic block을 매칭하기 위해 code checksum을 사용하는데, 이는 종종 순서에 의존한다. 이 경우 기존 instruction을 대체 instruction으로 reodering하거나 replacing하면 매칭이 실패한다.
CFG Altering
bindiff와 같은 일부 도구는 각 함수의 CFG 시그니처에 의존한다. fake node, edge, call을 추가하여 시그니처를 망치면 어떨까? 그러면 함수 시그니처가 수정되고 fixed points identifying 프로세스가 실패한다. 절대 취하지 않을 분기를 넣어 CFG를 깨뜨리고 CFG break를 기반으로 diffing 알고리즘을 만들 수 있다.
기능(:functionality)을 변경하지 않고 procedure의 CFG 또는 프로그램의 CG의 구조를 변경함으로써 구조 분석에 기반한 바이너리 diffing 분석 도구를 실패하게 만들 수 있다. 이 방법은 바이너리 매칭을 기반으로 하는 동형 분석에도 영향을 미친다. 각 바이너리에 대해 그래프 구조가 일치해야 하기 때문에 의미 없는 블록이나 instruction을 몇 개만 넣으면 함수 signaturing 프로세스가 혼란스러워진다. 주의할 점은 CFG mangling 블록을 충분한 수의 함수에 배치해야 한다는 것이다. 패치된 함수 주위에 집중되어 있으면 패치된 지점만 더 잘 보인다.
Use proxy call
Prevent CG Recognition
<XXX> 호출을 대체하여 <YYY>를 호출하면 YYY 함수는 다음과 같이 표시된다.
함수 YYY는 기본적으로 call proxy 이외의 기능이 없는 null 함수다. 바이너리 diffing의 디스어셈블러가 이 null 함수를 인식하는 경우 non-functioning garbage instruction을 넣어 디스어셈블러 또는 바이너리 differ를 속일 수 있다.
Call that never returns
실제로 이 아이디어는 RpcRaiseException이 CFG를 깨뜨리고 함수 매칭을 방해한 DarunGrim2가 속은 실제 사례와 함께 나왔있다. 이것은 CFG를 심각하게 깨뜨릴 것이다. 반환하지 않는 호출을 넣고, 그 "call XXX" instruction 옆에 함수 블록을 넣는다.
다음과 같이 instruction을 다음과 같이 바꾼다:
jzA다음과 같은 곳에:
1: call B
2: proc B:
3: add esp, 4
4: jzA호출은 반환되지 않으며 "jz A" 라인 옆에 있는 코드 부분은 해당 함수에 속하는 것으로 인식된다. 거기에 다른 힘수의 basic block을 배치하면 해당 함수의 블록 소유권 인식이 완전히 깨진다.
Sharing Basic Blocks
여러 함수가 basic block을 공유하면 CFG와 CG가 깨질 수 있다. 때때로 컴파일러는 여러 함수 간에 동일한 basic block을 공유하는 최적화를 수행한다. 공유 basic block에는 반환 basic block이 포함되어야 한다. 따라서 주어진 함수 쌍에 대해 동일한 이러한 종류의 basic block을 찾기가 쉽지 않다.
Use multiple heads for a function
함수에 여러 진입점을 만들면 디스어셈블러가 실제 함수 진입점과 효과적으로 혼동할 수 있다. fake function head(entry point)를 보다 현실적으로 만들기 위해 fake head를 호출하는 fake basic block을 만들 수 있다. 이것은 디스어셈블러가 fake head도 유효한 것이라고 믿도록 속일 것이다. 따라서 이것은 적절한 기능 블록 매칭을 방지하고 그래프 동형을 사용하여 바이너리 diffing에 영향을 미친다.
Anti Binary Diffing Tool: Hondon
우리는 "Hondon"(한국어로 혼돈을 의미함)이라는 사내 도구를 구현하여 주요 상용 및 프리웨어 바이너리 diffing 도구를 무력화할 수 있음을 보여줄 것이다. 난독화된 바이너리에 사용할 수 있으므로 패치된 포인트가 다른 의미 없는 difference 아래에 묻힌다. 난독화된 코드 부분은 모듈의 성능에 영향을 미치거나 디버깅을 어렵게 만들지 않아야 한다. 말하자면 바이너리 diffing을 방지하는 것 외에 심각한 부작용이 없어야 한다. 패치된 코드 부분을 보이지 않게 만들고 난독화된 가짜 패치 부분 사이에 묻힌다. Hondon은 여기에 제시된 대부분의 방법을 구현하고 있다. 그리고 IDA 플러그인으로 실행할 수 있다. IDA의 디스어셈블 능력에 달려 있다. IDA의 디스어셈블러가 잘못 해석한 것을 수동으로 수정할 수 있기 때문에 도구에 완전한 디스어셈블러가 있는 것보다 낫다. 자체 디스어셈블러를 제공한다면 피드백 프로세스를 거의 불가능하게 만들 것이다. 따라서 이것을 IDA의 플러그인으로 실행하면 대상 바이너리를 바이너리 diffing 방지 바이너리로 다시 작성한다.
Conclusion
그래서 우리는 바이너리 diffing art의 역사와 현재 상태를 살펴 보았다. 1-day exploit 위협은 현실이며 현재 패치가 있는 날마다 발생한다. 때때로 어떤 사람들은 예를 들어 IE6 및 IE7 바이너리와 같은 제품의 다른 버전을 비교하여 자동으로 수정된 일부 취약점을 찾는다. 그리고 취약점이 수정된 지점은 추가 취약점 헌팅을 위한 좋은 출발점이다. 버그는 집계되는 경향이 있으며 버그가 발견된 주변에 여러 번 다른 버그가 상주한다. 또는 일부 수정 사항이 불완전하여 누군가가 이러한 사실을 찾아 조건을 exploit할 수 있다.
따라서 공격 기술이 향상됨에 따라 보호 기술도 그에 따라 진화해야 한다. 일부 메이저 vendor는 심각한 형태의 안티 디버깅을 사용하는 것을 꺼린다. 왜냐하면 그것이 문제를 일으킬 수 있기 때문이다. 따라서 그들은 lightweight, non-aggressive, effective한 방법으로 바이너리 differ를 무력화하길 원한다. 바이너리 diffing의 약점을 노리는 "Hondon"을 소개했다. anti-binary diffing 기술이 발전함에 따라 binary differ도 진화할 것이다. 그들은 broken CFG를 처리하고 강력한 형태의 instruction reordergin을 수행하거나 다른 기술을 사용한다. 그래서 이야기는 계속 된다...
Uploaded by Notion2Tistory v1.1.0