Searching statically-linked vulnerable library functions in executable code
실행 가능한 코드에서 정적 링크된 취약한 라이브러리 함수 탐색
원문 : https://googleprojectzero.blogspot.com/2018/12/searching-statically-linked-vulnerable.html
역자 서문
이 포스팅 원문은 google project zero 블로그에 게시된 글로, “정적 링크된 취약한 라이브러리 함수 탐지”라는 주제의 글이다. 문서 초반에서는 오픈소스 라이브러리에 대한 전반적인 설명과, 같은 코드라도 컴파일러마다 다른 바이너리를 낳을 수 있음을 설명한다. 문서 중반 부터는 SimHashing이라는 알고리즘을 소개하며, 유사성을 보존하는 해시를 계산하는 방법을 설명한다. 또한, 머신 러닝과 SimHashing을 이용해 두 바이너리간 다른 점을 찾는 방법을 소개한다. 그러나 마지막에서는 이는 40% 정도만 신뢰할 수 있는 결과를 낳는다고 결론지으며, 그 방법을 개선할 여지가 많다고 설명한다. 더불어 머신 러닝 코드 수정 등 7가지 차후 과제들을 남기며 이 글을 마치고 있다.
해당 문서를 전반적으로 번역함과 동시에 SimHashing 알고리즘에 대해 자세히 알아보고, 데이터를 어떻게 학습시키고 변종 함수의 유사성을 어떻게 탐지하는지 알아보고자 한다.
요약
소프트웨어 공급 체인은 갈수록 복잡해지고 있으며, 실행 파일에서 취약한 써드파티 라이브러리의 정적 링크된 복사본을 탐지하기 어려워지고 있다. 이 글은 다른 실행 가능한 오픈 소스 라이브러리로부터 코드를 탐지하기 위해 아파치 라이센스 오픈 소스 라이브러리의 기술적 세부 사항을 토론한다. 마찬가지로 리얼 월드 소프트웨어의 오픈 소스 라이브러리 결과 또한 논의한다.
기술적 블로그 게시물
관대한 오픈 소스 라이브러리는 IT 업계에 큰 이익이 되어왔다. 대부분 일반적인 문제는 쉽게 재사용하고 통합할 수 있는 허가된 라이센스(BSD 또는 아파치)로 고품질 라이브러리를 사용하여 해결할 수 있다.
이것은 모두에게 좋은 일이었다.
그럼에도, 정적 링크된 써드파티 코드는 특별한 주의가 필요하다. 써드파티의 취약점이 정기적으로 발견되며, 이는 바이너리 업데이트 하는 것을 의미한다. 상위 라이브러리 변경 사항을 코드의 로컬 포크에 병합하는 경우 문제는 더 어려워진다. 모든 조직이 이런 권리를 누리는 것은 아니며, 심지어 성숙한 안전한 개발 프로세스를 갖춘 회사도 때론 실수한다.
리버스 엔지니어와 오펜시브 리서처들에게 정적 링크된 소프트웨어 라이브러리 취약점을 식별하는 것은 기회이자 과제이다.
- 기회 : 새로운 타겟을 식별하는데 큰 힘이 들지 않으며, 대상에서 취약점을 얻을 수 있는 방법을 제공하기 때문에 기회이다.
- 과제 : 이 작업을 수행하는데 사용 가능한 도구의 수가 아주 적어서 어려움이 있다. 일반적인 방법은 주로 “알려진 문자열 탐색”, “학습된 추측”, BinDiff 사용의 조합으로 이루어진다.
기술적 문제는 “가능한 비교적 넓은 공간으로 효율적인 fuzzy 탐색 수행”으로 표현될 수 있다. 컴파일러 차이, 최적화 변경, 코드 변경이 문제의 코드에 “노이즈”를 추가하기 때문에 fuzzy 탐색은 필수적이다.
학술 연구의 측면에서, 몇 가지 흥미로운 논문은 코드 임베딩을 근사 이웃 탐색과 결합하는 정교한 머신 러닝 기반 방법을 제안했다. 그들은 R^n의 코드 표현을 계산한 다음, 이런 접근법이 강력하고 세련돼 보이지만, 공개 구현은 존재하지 않으며, 실제 적용은 없었다고 말한다.
실용적인 측면에서, 리얼 월드에서 사용은 CFG 알고리즘으로부터 파생되어 왔다. 그러나 구조적 변화에 관대하지 않다는 단점이 있다. 최근 (SSTIC '18)에서는 다음 달에 코드를 이용할 수 있게 한다는 발표와 함께 신경망 기반 접근법이 제시되었다.
이 문서는 FunctionSimSearch를 설명한다. 이것은 파이썬 바인딩 아파치 라이센스 C++ 툴킷이며, 다음 아래 세 가지를 제공한다.
1. SimHashing을 기반으로 한 해시 함수의 효율적 구현을 해시 함수에서 디스어셈블 된 함수에서 128 비트 해시를 계산하고 유사성을 유지한다. 예를 들어, 두 함수의 "거리"는 단순히 두 해시 간의 해밍 거리를 계산하여 계산할 수 있다. (x64에 두 개의 XOR 및 두 개의 POPCNT 명령이 있음)
2. 128 비트 해시에서 가장 가까운 이웃 탐색을 허용하는 효율적인 탐색 색인을 제공한다.
3. 인간이 제공한 예제에서 좋은 해시 함수를 "학습"하는 데 사용할 수 있는 감독 된 머신 러닝 코드 - 해시에 따라 유사해야하는 일련의 함수와 유사하지 않아야 하는 일련의 함수가 주어지면 코드는 이 예제를 존중하려는 해시 함수를 제공한다.
좋은 fuzzy matching의 필요
모든 리버스 엔지니어는 서로 다른 컴파일러와 컴파일러 설정이 엄청나게 다른 어셈블리 코드를 생성할 수 있다는 것을 경험해왔다. 컴파일러는 CFG를 크게 변경하고, 코드를 이동할 수 있으며, 그 결과 아주 다른 디스어셈블 코드가 나온다.
예를들어, Visual Studio 2015와 gcc 6.4.0 (O1 최적화) 코드는 아래와 같다.
변경이 존재하는 상태에서 함수를 식별하는 좋은 방법이 필요하며, 명령어 수준과 그래프 수준의 변경을 모두 처리해야 한다는 것은 분명하다.
SimHashing 알고리즘의 이해와 그것이 제공하는 것
SimHashing은 Moses Charikar논문에 의해 소개되었으며, 원래는 웹페이지 중복 제거와 관련한 것이었다. 이것은 “지역 민감 해싱” 알고리즘 계열의 일부이다.
알고리즘 자체는 두 개의 해시 간의 해밍 거리가 원래 세트 간의 유사성을 근사하는 속성을 사용하여 값 집합을 해시로 압축하는 데 도움이 된다. 이렇게 하면 두 세트 사이의 유사성을 매우 빠르게 예측할 수 있다. (단지 XOR 및 POPCOUNT 연산을 통해).
어떻게 동작하는가? 주어진 일련의 무작위 128 비트 벡터 혹은 해시 피처(feature)를 입력하면 다음과 같이 최종 해시 출력을 계산한다.
1. 128 개의 부동 소수점 값 벡터를 모두 0으로 초기화한다.
2. 입력 세트 각 함수에 대해 다음을 수행한다.
a. 피처 비트 n이 0이면, n 번째 부동 소수점 값에서 1을 뺀다.
b. 피처 비트 n이 1이면, n 번째 부동 소수점 값에서 1을 더한다.
3. 양수 값을 1로, 음수 값을 0으로 매핑하여 부동 소수점 벡터를 128 비트 벡터로 변환한다.
왜 이것이 유사성 보존 해시를 생성할까? 직관적으로, 사소한 입력의 변화가 부동 벡터에 영향을 줄 수 있다. 이 벡터의 값은 평균 0과 분산 1/4의 피처 수로 대략 정규 분포된다.
몇몇 값들은 양수 음수 모두 0에 가까울 것이다. 세트를 약간 변경하면, 개별 값이 양수에서 음수로 또는 그 반대로 넘어갈 확률이 있다. 이 확률은 많은 세트 변경의 경우 점점 커진다. 작은 변경의 경우, 많은 비트가 플립될 확률은 비교적 낮다.
어떤 피처 세트가 계산되든 상관없이 결과가 항상 128비트 벡터가 된다는 점이 중요하다.
비교를 위한 좋은 피처 입력은 무엇인가? 이상적으로 우리는 “유사하다고 생각하는 것”을 대표하는 특징을 추출하기를 원한다. 예를 들어, 동일한 소스 코드에서 컴파일 되는 두 함수는 유사한 특징을 가져야 한다. 그것은 다소 알고리즘적으로 그러한 특징들을 설계하는 것과 관련이 있기 때문에, 현재로서는 문제의 특징들이 매우 간단하다. 바로 제어 흐름 그래프의 하위 그래프, 분해된 지침의 n-그램, 그리고 피연산자의 상수이다. 단순한 구현에서 모든 피처는 단위 가중치(weight)을 갖는다. 예를 들어, 모든 피처가 최종 해시에 동일한 역할을 한다는 식이다. 이것은 분명 이상적이지 않다. 함수 프롤로그는 두 함수의 유사성을 잘 나타내지 않는다. 그리고 우리는 나중에 이것을 개선할 것이다.
해시 탐색에 가장 가까운 간단한 근사치
주어진 입력 함수에 대한 유사성을 보존하는 해시를 계산하는 방법으로, 어떻게 우리가 “가장 유사한” 해시에 대해 유효한 단어 크기를 선정할 것인가?
지역 민감성 해싱의 두 번째 애플리케이션이 답이다. 인접한 두 지점이 동일한 해시 버킷에 담길 확률보다 더 큰 확률로 해시 함수 제품군을 구성할 수 있는 경우, 두 개의 원거리 포인트가 동일한 버킷에 담길 확률보다 더 큰 경우에 비교적 효율적인 가장 근접한 이웃 탐색을 해야한다. 입력 정보를 후보 버킷에 매핑하고 후보자를 처리하려면 단순히 k개의 다른 해시 함수군을 사용해야 한다.
지역 민감성 해시에 의한 랜덤 비트 선택
우리의 입력은 비트 벡터이므로, 그러한 해시 함수를 구축하는 가장 쉬운 방법은 벡터의 비트를 단순히 하위표본하는 것이다. 이것은 입력의 단일 랜덤 비트 레벨 정격이 해시군을 구성하기에 충분하다는 좋은 속성을 가지고 있다. k개의 다른 해시를 구성하려면, 비트 수준 치환을 입력에 k번 적용하고 처음 몇 개의 비트를 취해야 한다. 128비트의 비트 전송률은 소프트웨어에서는 저렴하고 하드웨어에서는 거의 무료다. 코드베이스에서 선택된 치환은 현대 CPU에서는 65주기로 실행되어야 한다.
자료구조 선택
기본적인 자료 구조는 다음과 같은 형식의 튜플의 순서 모음이다.
<Permutation Index, k번째 치환 입력 해시, result-id>
tuple <k, perm_k(입력) & (0xFFL << 56), 0>을 사용하여 이진 탐색을 수행하면 주어진 치환 인덱스 및 입력 값에 대한 해시 버킷이 제공된다. 우리는 그러한 k 탐색을 수행하고, 각각의 해시 버킷에 대해 후보 목록에 모든 요소를 추가한다. 각 후보와 입력 해시 사이의 해밍 거리가 계산되며, 결과는 해밍 거리의 순서로 반환될 수 있다.
캐시 메모리의 최대 버전은 단순히 이러한 튜플의 정렬된 배열 / 벡터를 사용한다. 우리의 목적과 효율적인 삽입을 위해 기존 C++ 코드는 메모리 매핑된 파일을 저장장치로 사용하여 영구적으로 만들어진 std::set 컨테이너와 같은 것을 사용한다.
예시를 통한 SimHashing 학습
설명한 접근법의 문제점 중 하나는 즉시 식별할 수 있다. 입력 세트의 모든 피처는 동일하게 중요하게 취급된다. 그러나 실제로는 피처가 크게 다르다. 다행히도, 개별 피처의 중요성을 SimHash 계산에 포함시키는 것은 쉽다. 즉, 부동의 벡터에 +1이나 -1을 추가하는 대신, 특정 피처의 가중치(weight)를 추가하거나 뺄 수 있다.
하지만 어떻게 하면 학습 데이터에서 좋은 가중치를 추론할 수 있을까? 컴파일러 변경 전반에 걸쳐 어떤 함수를 유지할 것인지 예측 가능한 함수를 통해 자동으로 “학습”할 수 있는가?
저렴한 변화 원리 사용
현대 머신 러닝의 역량은 자동적인 차별이다. 간단히 말해서, 자동 미분화는 “저렴한 변화 원리”를 제공하며, 이는 “R^n에서 R까지 함수를 계산할 수 있는 경우, 중간 오버헤드로 이 함수의 변화를 계산할 수 있다”로 비유할 수 있다. 이것은 우리가 가중치을 포함하는 손실 함수를 지정할 수 있다면, 우리는 이 손실 함수를 최소화하려고 노력할 수 있다는 것을 의미한다. 우리는 집합점에 대한 보장은 할 수 없지만, 예시로부터 가중치를 배울 수 있을 것이다.
그래서 우리에게 필요한 것은 라벨링된 데이터들과 좋은 손실 함수이다.
SimHash 거리를 위한 손실 함수 선정
거리를 위한 손실 함수를 구축하려면 약간 조심해야 한다. 우리의 최종 거리는 두 비트 벡터의 해밍 거리이기 때문에, 이 거리의 변화는 0이 될 가능성이 높다. 즉, 유용한 변화를 얻을 수 없는 많은 "평평한 부분"이 있다.
두 개의 실제 값이 동일한 부호를 가지고 있지 않을 때 양의 함수가 필요하고, 두 개의 실제 값이 동일한 경우 0 또는 음수가 필요하다. 이상적으로는 "동일 부호" 방향으로 입력을 이동하기 위해 기울기를 제공해야 한다.
먼저, 간단한 함수로 시작한다.
g(x,y) := -xyx2y2 + 1.0 + 1.0:
이 함수는 x와 y의 기호가 다르면 높은 손실을 가지며, 동일한 경우 0 손실을 갖는다. 불행히도, 대부분의 표면도 평평하다, 그래서 우리는 어떻게 해서든지 평평한 지역을 올바른 방향으로 향하게 할 필요가 있다. 그래서 우리는 d(x,y) :=(x-y)2 + 0.01과 곱한다.
이 함수는 우리의 필요조건을 만족시킨다. 원하는 방향으로 매개변수를 이동하고, 다른 기호를 없애며, x와 y가 동일한 기호를 가질 경우 손실이 없다.
요약하자면, 주어진 실제 벡터 쌍(각각 2진수 해시로 변환하는 마지막 단계 없이 해시 함수를 계산하여 얻은 값)의 경우, 각 벡터 항목의 손실을 간단히 합산할 수 있다. 우리는 이제 예를 통해 매개 변수를 조정하는 데 사용할 수 있는 손실 함수를 가지고 있다.
학습 데이터 생성
적어도 이론상으로는 학습 데이터를 생성하는 것이 간단해야 한다. 여러 컴파일러나 컴파일러 설정으로 일부 오픈 소스 코드를 컴파일하고 심볼 정보를 파싱하여 "함수 변형" 그룹을 만들 수 있어야 한다. 예를들어, 같은 C/C++ 함수에 대해 컴파일러가 다르면 출력도 다르다는 식이다.
안타깝게도 이론과 현실은 다르며, 많은 문제들이 있는데, 대부분은 심볼 파싱과 CFG 재구성에 관한 것이다.
리얼 월드 문제 : 심볼
다양한 버전의 Visual Studio를 사용할 때 자연스럽게 발생하는 PDB 파일 포맷의 다양한 버전을 분석하기 위한 크로스 플랫폼 도구의 가용성과, 많은 다른 컴파일러에 대해 동일한 오픈 소스 코드베이스를 안정적으로 구축하기 어렵다. GCC와 CLANG는 종종 대체가 불가능하지만, Visual Studio, GCC, CLANG에 개입하지 않고 구축하는 프로젝트는 훨씬 더 드물다.
안타깝게도, PDB 파싱 문제 해결책은 “포기”이며, 또 안타깝게도, Visual Studio와 GCC와 함께 동일한 코드베이스를 안정적으로 구축하는 문제의 해결책도 “포기”하는 것이다.
다른 문제는 다양한 망가진 C++ 컨벤션에 의해 발생하며, 다른 컴파일러의 다양한 컨벤션은 정확히 함수 이름에 영향을 미친다. 이는 GCC/CLANG와 Visual Studio 표기법 사이에 "통합"을 시도하고, 심볼에서 타입 정보를 제거하는 작은 도구로 해결된다.
리얼 월드 문제 : 신뢰할 수 있는 CFG 생성과 데이터셋 오염
함수 CFG를 얻는 것은 간단해야 한다. 실제로, 실험용 디스어셈블러는 다른 컴파일러와 플랫폼에 걸쳐 스위치 문을 올바르게 분기하지 않는다. 즉, 함수가 잘리고 기본 블록이 잘못 할당된다. 특히, -fPIE의 -fPIC를 사용하여 컴파일된 GCC 바이너리에 심각한 결과를 가져오는데, 이는 ASLR로 인해 현대 리눅스 시스템의 디폴트값이다.
최종 결과는 오염된 학습 데이터와 오염된 탐색 지표, 거짓 양수, 거짓 음수로 이어지고, 실무자들은 좌절한다.
이상적인 해결책은 보다 신뢰할 수 있는 어셈블리일 수 있지만, 실제로 이를 해결하기 위해서는 동일해야 하는 함수 사이에 극단적인 크기 불일치에 대해 신중하게 조사해야 하고, 학습 예제를 컴파일 할 때는 PIC와 PIE를 빼고 해야한다. (-fno-pie -fno-PIE -fno-pic -fno-PIC는 유용한 빌드 옵션이다.)
학습 / 검증 데이터 분리의 두 가지 방법
왜 코드가 여러 개의 다른 학습/검증 데이터를 분리해서 생성하는가? 왜냐하면 우리가 관심 있는 두 가지 질문이 있기 때문이다.
1. 우리가 학습한 함수의 변종을 탐지하는 능력을 학습 과정이 개선하는가?
2. 학습되지 않은 함수 버전에서도 대해서도 우리가 학습한 함수의 변종을 탐지하는 능력을 학습 과정이 개선하는가?
2번이 바람직하지만, 이 목표를 달성할 수 있을 것 같지는 않다. 우리의 목표인 정적 링크된 취약한 라이브러리 함수 탐지를 위해, 우리는 아마도 1번을 선택해야 할 것이다. 그러나 이러한 질문에 의미 있는 답을 하기 위해서는 학습 데이터와 검증 데이터를 다르게 분리할 필요가 있다.
2번을 확인하려면 학습 및 검증 데이터를 "함수 그룹"에 따라 나누어야 한다. "함수 그룹"은 동일한 함수의 변형 구현이다. 그런 다음 몇 개의 함수 그룹을 분리하고, 다른 함수 그룹을 학습하고, 우리가 분리한 그룹을 사용하여 검증해야 한다.
반면, 1번을 확인하려면, 랜덤 함수 변형을 분리하고, 나머지를 학습한 다음, 나머지를 학습하고, 분리된 함수를 더 잘 탐지하는지 확인해야 한다.
학습 데이터의 분할 방법은 다음과 같이 잘 설명된다.
실제 학습 과정 수행
일단 학습 데이터를 사용할 수 있으면, 학습 과정 수행은 아주 쉬워진다. Makefile 빌드 후 bin 디렉터리 아래에 있는 trainsimhashweights 바이너리를 실행하면 된다.
며칠 후 학습 과정은 현재 디렉터리에 20단계마다 L-BFGS의 스냅샷을 작성하면서 500회의 L-BFGS 반복을 수행하게 될 것이다.
이는 검증 데이터에 "유사 쌍과 이종 쌍 사이의 평균 거리 차이"를 제공한다. 코드는 유사한 쌍과 검증 데이터에서 다른 쌍 사이의 평균 거리를 계산하며, 두 쌍의 차이를 보여준다. 만약 학습이 효과가 있다면, 차이는 더 커질 것이다.
약 420개의 학습 단계를 초과 학습하기 시작하는 것을 볼 수 있다. 검증 세트의 평균 차이는 다시 조금씩 줄어들기 시작한다. 따라서 최적화 프로세스를 중지하는 것이 좋은 아이디어이다. 또한 “비슷한” 쌍과 “다양한” 쌍 사이의 평균 거리 차이가 10비트를 조금 넘는 수준에서 거의 25비트로 증가했음을 볼 수 있다. 이것은 학습 과정이 함수의 변종을 인식하는 능력을 향상시킨다는 것을 암시하는 것처럼 보인다.
시각화로서 t-SNE의 사용
고차원 시각화의 일반적인 방법으로 t-SNE가 있다. 이 방법은 거리 매트릭스를 수집하여 저차원(2d 또는 3d) 도형을 만드는 방법이다. 코드는 시각화하는 데 사용되는 작은 파이썬 스크립트도 사용된다.
두 가지 탐색 인덱스를 사용할 것인데, 한 개는 “학습된 피처 가중치”이고, 다른 하나는 “단일 피처 가중치”이다.
d3.js를 이용해 렌더링 한 내용은 아래와 같다.
단일 피처 가중치:
학습된 가중치:
마우스 포인터를 올리면 함수 심볼과 원본 파일이 표시된다. (본 문서에서는 이미지이므로 표시되지 않고, 원문-google project zero 블로그에서는 표기됨) 우리의 학습이 함수 그룹들을 "더 밀접하게" 그룹화한 한 것을 육안으로 확인할 수 있다.
여기서 우리는 학습이 어느 정도 효과가 있지만 모든 함수에 동일한 영향을 미치지는 않는다는 것을 알 수 있다. 몇몇 함수들은 다른 함수들보다 학습된 것 보다 더 많은 이점이 있다. 그리고 왜 그러한지에 대해서 이제 조사가 필요하다.
TPR, FPR, IRR, and the ROC-곡선 시험
정보 탐색 시스템을 평가할 때 다양한 지표가 중요하다. 다음과 같은 사항들이 중요하다.
- 긍정적 비율 : 찾기로 되어 있던 결과 중 몇 개를 찾기로 되어 있지 않았는가?
- 부정적 비율 : 찾지 않아야 했던 결과 중 몇 개를 찾았는가?
- 무관한 비율 : 우리가 반환한 결과의 몇 퍼센트가 관련이 없는가?
이것은 정밀도(precision) 및 ROC 곡선(FPR에 대한 TPR 도표)이다.
깃허브에 있는 파이썬 코드로 ROC 곡선을 그릴 수 있다. 이 스크립트는 탐색 인덱스의 모든 요소에 대한 기호, 탐색 인덱스의 텍스트 표시(dumpsearchindex 포함), 실제 탐색 인덱스 파일에 대한 접근을 필요로 한다.
학습된 데이터와, 학습된 데이터 모두 곡선을 그릴 수 있고, gnuplot을 통해 도표를 그릴 것이다.
먼저, 아래는 학습되지 않는 결과이다.
학습 과정으로 곡선에 얼마나 영향이 미쳤을까?
현재의 형태로, 학습은 학습 없이 달성할 수 있는 결과보다 부적절한 결과 비율을 낮추는 데 유용하다. 그러나, 학습 없이 달성할 수 있는 부적절한 결과의 비율에 대해서는 학습되지 않은 버전이 더 나은 결과를 낳는 것으로 보인다.
실제 탐색
파이썬 가능한 RE 도구에서 FunctionSimSearch 함수 사용
커맨드라인 도구는 대부분 디스어셈블리를 위해 DynInst에 의존하지만 리버스 엔지니어는 당황스러울 정도로 다양한 도구를 사용한다. (IDA, Radare, Binary Ninja, Morth 등)
이러한 모든 도구의 통합 개발 도구를 고려할 때, 가장 간단한 것은 파이썬 바인딩을 제공하는 것이라고 판단했고, 그래서 파이썬 인터프리터와 상호작용할 수 있는 모든 도구는 동일한 API를 통해 FunctionSimSearch를 사용할 수 있다.
mpengine.dll에서 unrar 코드 탐색
IDA를 사용하여 mpgine.dll에서 통해 우리가 인식할 수 있는 함수를 검색할 것이다.
FunctionSimSearch를 사용하여 기존 디스어셈블리에서 “/var/tmp/ida2/simhash.index” 탐색 인덱스를 덧붙일 수 있다.
결과들 중 몇 가지를 좀 더 심도 있게 살펴보자. 첫 번째 결과는 128비트 중 125비트가 일치하는 memcpy_s 버전을 발견했다. 이것은 매우 가까운 일치를 의미한다. 해당 디스어셈블리는 다음과 같다.
사소한 변경 외에도, 두 함수는 분명히 동일하다. CFG 구조도 동일하게 유지되었다.
아래는 그 다음 결과이다.
디스어셈블리가 약간 바뀌었지만, CFG 구조는 거의 비슷하다.
다음 예시는 훨씬 큰 함수이다. 그래프는 어떻게 보이는가?
그래프는 상당히 바뀌었지만, 약간의 서브 그래프는 안정된 상태로 남아있다. 더 나아가, 코드에는 0x17D7840나 0x36와 같은 매직 상수가 남아있다. 이것든 해시 전반적으로 남아있으며 이는 대단한 발견이다.
Adobe Reader에서 libtiff 코드 탐색
과거에 Adobe Reader가 구식 libtiff를 사용했다는 것은 잘 문서화 되었다. 이것은 AcroForm.dll을 통해 탐색을 실행하면 libtiff의 많은 좋은 결과 얻을 수 있을 것이고, 이를 달성하지 못하면 별로 기분이 좋지 않을 것이다.
내 윈도우즈 DLL에서 libtiff 코드 탐색
우리가 이미 알고 있는 코드를 찾는 것은 별로 흥미롭지 않다. Windows 10이 설치된 전체 하드 디스크에서 libtiff의 흔적을 검색하는 것은 어떨까?
이를 명령어로 수행하려면 몇 가지 사항이 필요하다.
1. 다양한 버전의 Visual Studio와 다양한 컴파일러 설정으로 libtiff를 컴파일한 디렉터리
2. PDB 파일에서 우리가 쉽게 파싱할 수 있는 포맷의 디버깅 정보. Microsoft의 DIA2Dump 도구를 사용하여 출력을 텍스트 파일로 리디렉션해 PDB 파일과 동일한 디렉터리에 있는 .debugdump 파일
WindowsCodecs.dll와 libtiff.dll을 로드하여 IDA로 매칭시켜보자.
이렇게 보면 정말 완전 다르게 생겼다. 그러나 확대해보면, 상당히 상당히 비슷한 것을 볼 수 있다.
결과로부터 얻을 수 있는 것은, IDA가 얻어낸 Microsoft가 제공한 PDB디버그 심볼 이름은 PackBitsEncode이라는 것이다.
WindowsCodecs.dll에 대한 자세한 내용은 Microsoft가 크게 변경한 libtiff 3.9.5버전의 포크를 포함하고 있다는 것을 보여준다. 우리는 마이크로소프트가 어떻게 상위 라이브러리 보안 및 안정성 문제를 보고하는지 조사하지 않았다. libtiff는 libjpeg에 링크되어있기 때문에, 동일한 DLL에 수정된 libjpeg포크도 포함되어 있다는 것은 놀라운 일이 아니다.
요약, 앞으로의 방향, 향후 과제
이 작은 연구에서 무엇을 배웠는가? 유사성을 보존하는 해시 생성과 그 해시들에 대한 탐색에 관한 많은 세부사항 외에도, 몇 가지 흥미로운 교훈을 배웠다.
교훈
탐색 인덱스 vs 선형 검색 - 현대의 CPU는 XOR이 빠르다
현대의 CPU는 큰 메모리 영역에 걸쳐 선형 탐색을 수행하는 데 매우 빠른 것으로 밝혀졌다. “가장 가까운”값의 인덱스를 기억하는 내부 루프가 있는 작은 C 프로그램은 단일 코어에서 수억 개의 해시를 검색하며, 해시를 로드한 값에 대해 XOR을 적용하고 결과 비트를 연산한다.
지역 민감 해싱에 대한 알고리즘은 수억 해시가 될 때까지 도달하지 않는다. 얼마나 많은 사람들이 비교할 해시를 가질지 조차도 불분명하다.
똑똑한 탐색 인덱스는 과도하게 설계되었을 가능성이 있으며, 단순한 선형 탐색도 잘 될 것이다.
단순 문자열 검색과의 경쟁
정적 링크된 라이브러리를 찾는 데 있어 명시된 문제에 대해서는 대부분의 경우(개인적으로 90% 이상) 라이브러리의 일부인 특정 표현식 문자열을 검색하는 것이 가장 효과적인 방법인 것으로 나타났다. 컴파일러는 일반적으로 문자열을 변경하지 않으며, 문자열이 충분히 이상한 경우 거의 0의 무관한 결과와 상당히 높은 참의 비율을 얻을 것이다.
따라서 우리가 여기서 탐구한 무거운 코드는 오픈소스 라이브러리 사이에 개별 코드를 잘라 붙여 넣는 상황에서 가장 유용하다. 우리가 조사한 리얼 월드 사례들 중에서 mpengine.dll만이 그 규칙에 부합한다.
기존에 발표된 결과와 관련된 흥미로운 연구 질문도 있다: 간단한 문자열 검색보다 이 방법이 좋은 점은 무엇인가?
문제는 아직 여전히 어렵다
이렇게 수행되는 모든 계산에도 불구하고, 전체 경우의 약 40%만 안정적이고 신뢰할 수 있는 결과를 낳는다. 만약 우리가 컴파일러에 접근할 수 없는 경우에 그 수는 더 적어질 것이다. 방법을 개선할 여지가 많다. 낙관적으로는, 관련이 없는 적은 수의 결과만 가지고는 90% 이상에 도달할 수 있어야 한다고 생각한다.
향후 과제
앞으로 나아가고 확장되어야 할 몇 가지 방향이 있다.
1. 텐서플로우에서 머신 러닝 코드를 다시 작성해야 한다. 손실 함수를 C++에 직접 쓰고 싶었기 때문에, 현재 코드로는 56코어 서버 시스템으로 학습하는 데 며칠이 걸린다. 이것은 단일 언어 코드베이스의 구조에서는 우아하지만, GPU에 학습 과정을 쉽게 병렬화할 수 있는 언어를 사용하면 미래의 실험은 훨씬 쉬워진다.
2. L-BFGS을 현대 머신 러닝에 사용되는 일반적인 SGD 모델과 바꾼다. 학습 데이터의 양이 증가함에 따라, L-BFGS는 잘 확장되지 않는다, 방대한 양의 데이터 학습에 대해 그것이 더 이상 사용되지 않는 데에는 다 이유가 있다.
3. 트리플, 쿼드러플 학습. 데이터에서 내장 임베드를 배우는 것을 다루는 여러 최신 논문들은 직관적 관점에서 이치에 맞으며, 학습 코드는 그러한 학습을 허용하도록 조정되어야 한다.
4. 더 나은 피처가 필요하다. 현재 사용되는 피처들은 매우 빈약하다. 피연산자, 구조 오프셋, 문자열 등은 모두 무시된다. 그러나 여기에는 분명히 많은 가치있는 정보가 있다.
5. 그래프-NN 실험. ‘그래프 학습’에 대한 많은 연구가 수행되었고 머신 러닝 커뮤니티에서 발표되었다. 결과를 살펴보면 아주 흥미롭다. 예제를 통해 단순 경로와 같은 그래프 알고리즘을 매우 단순하게 학습할 수 있으며, 이러한 모델들은 탐색한 단순한 선형 모델을 능가할 수 있다. CCS '17은 이런 모델을 사용하며, 문자열 매칭으로 인한 성능 부분과 모델의 나머지 부분이 무엇인지 판단하기가 어렵더라도 접근방식은 유망하며 유효하다.
6. 인접한 정보 사용. 다른 라이브러리에서 가져온 함수는 바이너리에 인접한 경향이 있다.
7. ANN 트리 자료 구조를 배열로 교체. 메모리를 선형적으로 교체하는 현대 CPU의 속도를 고려할 때, 대다수의 사용자(100m 해시 미만)는 ANN 검색(및 그로 인한 스토리지 오버헤드)을 위해 복잡한 데이터 구조를 요구하지 않을 가능성이 높다. 대부분의 경우 단순한 선형 탐색은 LSH 계열의 비트 치환보다 우수해야 한다.
마무리
질문 및 권장 사항이 있으면, 주저하지 말고 관련 깃허브 리포지터리로 연락 바란다.