在逆向工程、惡意軟件分析和二進制文件解析領域,快速準確地識別特定字節模式(即“簽名”)是一項核心任務。本文將圍繞一款基于PE-bear工具的二進制簽名查找器,深入解析其設計思路、實現原理及相關技術背景,揭示其如何高效解決帶通配符的多模式匹配問題。
一、功能概述:什么是二進制簽名查找器?
二進制簽名查找器的核心功能是在一段二進制數據(如PE文件、內存鏡像等)中,快速定位符合預設“簽名”的字節序列。這里的“簽名”不僅包括固定的字節模式,還支持通配符(用?
表示),可靈活匹配“部分固定、部分可變”的字節序列。
例如,簽名40 ?? 4? 8? e?
表示:
- 第一個字節必須為
0x40
; - 第二個字節任意(
??
); - 第三個字節的高4位為
0x4
(4?
); - 第四、五個字節的高4位分別為
0x8
和0xe
(8?
和e?
)。
該工具支持單模式匹配、多模式同時匹配,還可從外部文件(SIG格式)加載簽名列表,廣泛應用于:
- 逆向工程中識別已知函數序言(如
0x55 0x48 0x8B 0xec
是x64函數的典型序言); - 惡意軟件分析中檢測特征碼;
- PE文件解析中定位特定結構(如導入表、節表)。
二、核心設計思路:從“樸素匹配”到“智能優化”
該工具的設計圍繞“高效匹配”展開,通過對比“樸素匹配”與“基于樹結構的多模式匹配”,最終選擇后者作為核心方案。其設計思路可總結為三個關鍵目標:
1. 解決多模式匹配的效率問題
樸素匹配(Naive Matching)的思路是:對每個待匹配的模式,逐個掃描二進制數據,通過memcmp
對比是否匹配。例如,若要同時查找10個模式,需對數據進行10次完整掃描,時間復雜度為O(k*n)
(k
為模式數量,n
為數據長度)。當模式數量增加或數據量龐大時(如GB級內存鏡像),這種方式效率極低。
為解決此問題,工具采用了多模式匹配算法,核心是通過“一次掃描數據,匹配所有模式”,將時間復雜度優化為O(n + m + z)
(m
為所有模式總長度,z
為匹配結果數量)。
2. 支持通配符的靈活匹配
二進制數據中,許多特征模式并非完全固定(如包含動態計算的地址、版本號)。例如,某函數調用的指令為E8 ?? ?? ?? ??
(E8
是調用指令,后4字節為相對偏移,每次運行可能不同)。
工具通過“掩碼(Mask)”機制支持通配符:為每個簽名定義一個與字節序列等長的掩碼,掩碼中0xFF
表示對應字節需精確匹配,0x00
(或其他值)表示該字節為通配符(可忽略)。例如,簽名55 0? 34 12
的掩碼為0xFF 0x0F 0xFF 0xFF
,表示第二個字節的低4位可變。
3. 兼顧易用性與可擴展性
工具設計了清晰的簽名管理機制:
- 支持直接在代碼中定義簽名(如
addPattern
方法); - 支持從文本格式解析簽名(如
loadFromByteStr
方法解析"40 ?? 4? 8? e?"
); - 支持從外部SIG文件加載簽名(包含名稱、長度和字節定義),便于動態更新簽名庫。
三、實現原理:基于Aho-Corasick自動機的匹配機制
工具的高效匹配能力源于對Aho-Corasick自動機的應用。這是一種專為多模式匹配設計的算法,本質是通過構建“前綴樹+失敗鏈接”,實現一次掃描完成所有模式的匹配。
1. 核心數據結構:前綴樹(Trie)與節點(Node)
- 前綴樹:將所有模式的字節序列按前綴共享原則構建成樹。例如,模式
CAT
和CATC
可共享前綴C-A-T
,樹中每個節點代表一個字節,路徑代表模式的前綴。 - 節點(Node):每個節點存儲:
- 子節點指針(指向后續字節);
- 失敗鏈接(用于匹配失敗時跳轉,類似KMP算法的“部分匹配表”);
- 匹配到的模式列表(若當前節點是某模式的結束,則記錄該模式)。
2. 算法執行步驟
(1)構建前綴樹
將所有待匹配的簽名(模式)插入前綴樹。例如,插入"CAT"
和"CATC"
時,先插入C->A->T
(標記CAT
為匹配模式),再從T
延伸出C
(標記CATC
為匹配模式)。
(2)構建失敗鏈接
失敗鏈接的作用是:當匹配到當前節點后,若下一個字節不匹配,可通過失敗鏈接跳轉到“最長公共后綴”節點,避免重新掃描前綴。例如,若當前匹配到C-A-T
,下一個字節不是C
,則通過失敗鏈接跳轉至其他以T
為結尾的前綴(如BAT
的T
節點),繼續匹配。
(3)掃描數據并匹配
對輸入的二進制數據進行一次遍歷:
- 從根節點開始,根據當前字節沿子節點移動;
- 若子節點不存在,通過失敗鏈接跳轉,重復此過程;
- 每到達一個節點,檢查其關聯的模式列表,記錄所有匹配結果(偏移量、模式名稱等)。
3. 通配符的處理機制
在Aho-Corasick框架中,通配符通過“模糊匹配”實現:當比較當前字節與節點字節時,若簽名中該位置為通配符(掩碼對應位置為0x00
),則直接視為匹配,無需檢查實際字節值。例如,對于模式40 ?? 4?
,第二個字節任意匹配,第三個字節僅檢查高4位是否為0x4
。
四、關鍵技術點與領域知識
1. 模式匹配算法的選擇
算法 | 適用場景 | 時間復雜度 | 工具中的應用 |
---|---|---|---|
樸素匹配 | 單模式、短數據 | O(n*m) | 作為基準測試(naive_search 函數) |
KMP | 單模式、長數據 | O(n + m) | 未直接使用,但其“部分匹配”思想被失敗鏈接借鑒 |
Aho-Corasick | 多模式、任意數據量 | O(n + m + z) | 核心算法(tree_search 、tree_count 函數) |
工具通過對比測試(如naive_search
與tree_search
的結果一致性驗證),證明了Aho-Corasick在多模式場景下的效率優勢。
2. 二進制簽名的工程化表示
工具將簽名抽象為Signature
類,包含:
- 名稱(用于標識模式,如“ASProtect v1.1 MTEc”);
- 字節序列(原始字節數組);
- 掩碼(通配符定義);
- 輔助方法(如
toByteStr
將字節序列轉為字符串,loadFromFile
從SIG文件加載)。
這種抽象使簽名的管理、解析和匹配解耦,便于擴展(如支持新的通配符格式)。
3. 相關領域背景
- 逆向工程:函數序言(Prolog)、指令序列等固定模式是識別代碼結構的關鍵,工具中
patterns32
和patterns64
即預定義了x86/x64架構的常見函數序言。 - 惡意軟件分析:特征碼(Signature-based Detection)是傳統殺毒軟件的核心技術,工具可通過加載病毒特征庫快速定位惡意代碼。
- PE文件解析:PE文件的頭部、節表、導入表等結構有固定簽名(如
MZ
頭、PE\0\0
標記),工具可用于定位這些結構。
五、測試設計:確保正確性與可靠性
namespace sig_finder {inline size_t find_all_matches(Node& rootN, const BYTE* loadedData, size_t loadedSize, std::vector<Match>& allMatches){if (!loadedData || !loadedSize) {return 0;}rootN.getMatching(loadedData, loadedSize, allMatches, false);return allMatches.size();}inline Match find_first_match(Node& rootN, const BYTE* loadedData, size_t loadedSize){Match empty;if (!loadedData || !loadedSize) {return empty;}std::vector<Match> allMatches;rootN.getMatching(loadedData, loadedSize, allMatches, true);if (allMatches.size()) {auto itr = allMatches.begin();return *itr;}return empty;}};...namespace sig_finder {class Node{public:Node(): level(0), val(0), mask(MASK_IMM),wildcard(nullptr), immediates(0x100),partialsL(0x10), partialsR(0x10),sign(nullptr){}Node(BYTE _val, size_t _level, BYTE _mask): val(_val), level(_level), mask(_mask),wildcard(nullptr), immediates(0x100), partialsL(0x10), partialsR(0x10),sign(nullptr){}~Node(){clear();}void clear(){_deleteChildren(immediates);_deleteChildren(partialsL);_deleteChildren(partialsR);if (wildcard) delete wildcard;wildcard = nullptr;if (sign) delete sign;sign = nullptr;}bool isEnd(){return (!immediates.size() && !partialsL.size() && !partialsR.size() && !wildcard) ? true : false;}bool isSign(){return sign ? true : false;}size_t addPatterns(const std::vector<Signature*>& signatures){size_t loaded = 0;for (auto itr = signatures.begin(); itr != signatures.end(); ++itr) {const Signature* sign = *itr;if (!sign) continue;if (this->addPattern(*sign)) {loaded++;}}return loaded;}bool addPattern(const char* _name, const BYTE* pattern, size_t pattern_size, const BYTE* pattern_mask = nullptr);bool addTextPattern(const char* pattern1){return addPattern(pattern1, (const BYTE*)pattern1, strlen(pattern1));}bool addPattern(const Signature& sign){return addPattern(sign.name.c_str(), sign.pattern, sign.pattern_size, sign.mask);}size_t getMatching(const BYTE* data, size_t data_size, std::vector<Match>& matches, bool stopOnFirst, bool moveStart = true);private:Node* getNode(BYTE _val, BYTE _mask);Node* addNext(BYTE _val, BYTE _mask);Node* _findInChildren(ShortMap<Node*>& children, BYTE _val){if (!children.size()) {return nullptr;}Node* next = nullptr;children.get(_val, next);return next;}bool _followMasked(ShortList<Node*>* level2_ptr, Node* curr, BYTE val, BYTE mask){Node* next = curr->getNode(val, mask);if (!next) {return false;}return level2_ptr->push_back(next);}void _followAllMasked(ShortList<Node*>* level2_ptr, Node* node, BYTE val){_followMasked(level2_ptr, node, val, MASK_IMM);_followMasked(level2_ptr, node, val, MASK_PARTIAL_L);_followMasked(level2_ptr, node, val, MASK_PARTIAL_R);_followMasked(level2_ptr, node, val, MASK_WILDCARD);}void _deleteChildren(ShortMap<Node*>& children){size_t startIndx = children.start();size_t endIndx = startIndx + children.maxSize();for (size_t i = startIndx; i < endIndx; i++) {Node* next = nullptr;if (children.get(i, next)) {delete next;children.erase(i);}}}Signature* sign;BYTE val;BYTE mask;size_t level;ShortMap<Node*> immediates;ShortMap<Node*> partialsL;ShortMap<Node*> partialsR;Node* wildcard;};};
...
void print_results(const char desc[], size_t counter, size_t timeInMs)
{float seconds = ((float)timeInMs / 1000);float minutes =((float)timeInMs / 60000);std::cout << desc << ":\n\t Occ. counted: " << std::dec << counter << " Time: "<< timeInMs << " ms.";if (seconds > 0.5) {std::cout << " = " << seconds << " sec.";}if (minutes > 0.5) {std::cout << " = " << minutes << " min.";}std::cout << std::endl;
}size_t find_matches(Node &rootN, BYTE loadedData[], size_t loadedSize, const char desc[], bool showMatches, bool showHexPreview = false)
{std::string inputStr((char*)loadedData);std::cout << "Input: " << inputStr << " : " << loadedSize << std::endl;std::vector<Match> allMatches;DWORD start = GetTickCount();size_t counter = find_all_matches(rootN, loadedData, loadedSize, allMatches);DWORD end = GetTickCount();for (auto itr = allMatches.begin(); itr != allMatches.end(); ++itr) {Match m = *itr;if (showMatches) {std::cout << "Match at: " << std::hex << m.offset << ", size: " << m.sign->size() << " : \"" << m.sign->name << "\"";if (showHexPreview) {std::cout << "\t";show_hex_preview(loadedData, loadedSize, m.offset, m.sign->size());}std::cout << std::endl;}}print_results(desc, counter, (end - start));return counter;
}size_t count_patterns(BYTE* buffer, size_t buf_size, BYTE* pattern_buf, size_t pattern_size)
{size_t count = 0;for (size_t i = 0; (i + pattern_size) < buf_size; i++) {if (memcmp(buffer + i, pattern_buf, pattern_size) == 0) {count++;}}return count;
}size_t naive_count(BYTE* loadedData, size_t loadedSize)
{t_pattern patterns[_countof(patterns32) + _countof(patterns64) + 1] = { 0 };// init patterns list:size_t i = 0;for (size_t k = 0; k <_countof(patterns32); k++, i++){const t_pattern& p = patterns32[k];patterns[i].ptr = p.ptr;patterns[i].size = p.size;}for (size_t k = 0; k < _countof(patterns64); k++, i++){const t_pattern& p = patterns64[k];patterns[i].ptr = p.ptr;patterns[i].size = p.size;}const char text_pattern[] = "module";patterns[i].ptr = (BYTE*)text_pattern;patterns[i].size = strlen(text_pattern);// search through the list:size_t counter = 0;DWORD start = GetTickCount();for (DWORD i = 0; i < _countof(patterns); i++) {const t_pattern& p = patterns[i];if (!p.ptr) continue;counter += count_patterns(loadedData, loadedSize, p.ptr, p.size);}DWORD end = GetTickCount();print_results(__FUNCTION__, counter, (end - start));return counter;
}size_t tree_count(BYTE* loadedData, size_t loadedSize)
{Node rootN;// init patterns list:for (size_t i = 0; i < _countof(patterns32); i++) {const t_pattern& pattern = patterns32[i];std::string name = "prolog32_" + std::to_string(i);rootN.addPattern(name.c_str(), pattern.ptr, pattern.size);}for (size_t i = 0; i < _countof(patterns64); i++) {const t_pattern& pattern = patterns64[i];std::string name = "prolog64_" + std::to_string(i);rootN.addPattern(name.c_str(), pattern.ptr, pattern.size);}rootN.addTextPattern("module");// search through the list:std::vector<Match> allMatches;DWORD start = GetTickCount();size_t counter = find_all_matches(rootN, loadedData, loadedSize, allMatches);DWORD end = GetTickCount();print_results(__FUNCTION__, counter, (end - start));return counter;
}size_t naive_search(BYTE* loadedData, size_t loadedSize)
{const BYTE pattern[] = { 0x40, 0x53, 0x48, 0x83, 0xec };size_t counter = 0;DWORD start = GetTickCount();for (size_t i = 0; i < loadedSize; i++) {if ((loadedSize - i) >= sizeof(pattern)) {if (::memcmp(loadedData + i, pattern, sizeof(pattern)) == 0) counter++;}}DWORD end = GetTickCount();print_results(__FUNCTION__, counter, (end - start));return counter;
}size_t tree_search(BYTE* loadedData, size_t loadedSize)
{Node rootN;const BYTE pattern[] = { 0x40, 0x53, 0x48, 0x83, 0xec };rootN.addPattern("pattern", pattern, sizeof(pattern));std::vector<Match> allMatches;DWORD start = GetTickCount();size_t counter = find_all_matches(rootN, loadedData, loadedSize, allMatches);DWORD end = GetTickCount();print_results(__FUNCTION__, counter, (end - start));return counter;
}void multi_search(BYTE* loadedData, size_t loadedSize)
{Node rootN;const BYTE pattern[] = { 0x40, 0x53, 0x48, 0x83, 0xec };rootN.addPattern("prolog32_1", pattern, sizeof(pattern));const BYTE pattern2[] = { 0x55, 0x48, 0x8B, 0xec };rootN.addPattern("prolog32_2", pattern2, sizeof(pattern2));const BYTE pattern3[] = { 0x40, 0x55, 0x48, 0x83, 0xec };const BYTE pattern3_mask[] = { 0xFF, 0x00, 0xF0, 0xF0, 0xF0 };Signature sign("prolog32_3", pattern3, sizeof(pattern3), pattern3_mask);std::cout << sign.name << " : " << sign.toByteStr() << "\n";rootN.addTextPattern("module");Signature* sign1 = Signature::loadFromByteStr("prolog1", "40 ?? 4? 8? e?");std::cout << sign1->name << " : " << sign1->toByteStr() << "\n";if (!sign1) {std::cout << "Could not load the signature!\n";return;}rootN.addPattern(*sign1);find_matches(rootN, loadedData, loadedSize, __FUNCTION__, false);
}bool aho_corasic_test()
{Node rootN;BYTE loadedData[] = "GCATCG";size_t loadedSize = sizeof(loadedData);rootN.addTextPattern("ACC");rootN.addTextPattern("ATC");rootN.addTextPattern("CAT");rootN.addTextPattern("CATC");rootN.addTextPattern("GCG");if (find_matches(rootN, loadedData, loadedSize, __FUNCTION__, true) == 3) {return true;}std::cerr << "[-]" << __FUNCTION__ << " : Test failed.\n";return false;
}bool aho_corasic_test2()
{Node rootN;BYTE loadedData[] = "ushers";size_t loadedSize = sizeof(loadedData);rootN.addTextPattern("hers");rootN.addTextPattern("his");rootN.addTextPattern("he");rootN.addTextPattern("she");if (find_matches(rootN, loadedData, loadedSize, __FUNCTION__, true) == 3) {return true;}std::cerr << "[-]" << __FUNCTION__ << " : Test failed.\n";return false;
}bool aho_corasic_test3()
{Node rootN;BYTE loadedData[] = "h he her hers";size_t loadedSize = sizeof(loadedData);rootN.addTextPattern("hers");if (find_matches(rootN, loadedData, loadedSize, __FUNCTION__, true) == 1) {return true;}std::cerr << "[-]" << __FUNCTION__ << " : Test failed.\n";return false;
}bool aho_corasic_test4()
{Node rootN;BYTE loadedData[] = "hehehehehe";size_t loadedSize = sizeof(loadedData);rootN.addTextPattern("he");rootN.addTextPattern("hehehehe");if (find_matches(rootN, loadedData, loadedSize, __FUNCTION__, true) == 7) {return true;}std::cerr << "[-]" << __FUNCTION__ << " : Test failed.\n";return false;
}bool aho_corasic_test5()
{Node rootN;BYTE loadedData[] = "something";size_t loadedSize = sizeof(loadedData);rootN.addTextPattern("hers");rootN.addTextPattern("his");rootN.addTextPattern("he");if (find_matches(rootN, loadedData, loadedSize, __FUNCTION__, true) == 0) {return true;}std::cerr << "[-]" << __FUNCTION__ << " : Test failed.\n";return false;
}bool sig_check()
{const BYTE test_pattern[] = { 0x54, 0x45, 0x53, 0x54 };const BYTE test_mask[] = { 0xFF, 0xFF, 0xFF, 0xFF};Signature test1("test1", test_pattern, sizeof(test_pattern), test_mask);Signature test2("test2", test_pattern, sizeof(test_pattern), nullptr);if (test2 != test1) {std::cerr << "[-] " << __FUNCTION__ << " : Test failed.\n";return false;}std::cout << "[+] " << __FUNCTION__ << " : Sign test 1 OK\n";const BYTE test_mask3[] = { 0xFF, 0x0F, 0xFF, 0xFF };Signature test3("test3", test_pattern, sizeof(test_mask3), nullptr);if (test1 != test3) {std::cerr << "[-] " << __FUNCTION__ << " : Test failed.\n";return false;}std::cout << "[+] " << __FUNCTION__ << " : Sign test 2 OK\n";return true;
}int main(int argc, char *argv[])
{if (argc < 2) {if (!aho_corasic_test()) return (-1);if (!aho_corasic_test2()) return (-1);if (!aho_corasic_test3()) return (-1);if (!aho_corasic_test4()) return (-1);if (!aho_corasic_test5()) return (-1);if (!sig_check()) return (-1);std::cout << "[+] All passed.\n";std::cout << "To search for hardcoded patterns in a file use:\nArgs: <input_file>\n";return 0;}size_t loadedSize = 0;BYTE* loadedData = load_file(argv[1], loadedSize);if (!loadedData) {std::cout << "Failed to load!\n";return 1;}if (argc < 3) {size_t nRes = naive_search(loadedData, loadedSize);size_t tRes = tree_search(loadedData, loadedSize);if (nRes != tRes) {std::cerr << "[-] Test failed.\n";return (-2);}std::cout << "---\n";nRes = naive_count(loadedData, loadedSize);tRes = tree_count(loadedData, loadedSize);if (nRes != tRes) {std::cerr << "[-] Test failed.\n";return (-2);}std::cout << "---\n";multi_search(loadedData, loadedSize);std::cout << "[+] Finished.\n";std::cout << "To search for external patterns in a file use:\nArgs: <input_file> <patterns_file>\n";return 0;}std::cout << "---\n";std::vector<Signature*> signatures;size_t loaded = 0;if (!(loaded = sig_finder::Signature::loadFromFile(argv[2], signatures))) {std::cerr << "Could not load signatures from file!\n";return 2;}std::cout << "Loaded: " << loaded << "\n";Node rootN;rootN.addPatterns(signatures);find_matches(rootN, loadedData, loadedSize, "from_sig_file", false);std::cout << "[+] Finished.\n";return 0;
}
工具通過多組測試驗證核心功能,體現“測試驅動設計”思想:
- 功能測試:如
aho_corasic_test
系列函數,驗證不同字符串(如"GCATCG"
、"ushers"
)中模式匹配的數量是否符合預期; - 邊界測試:如
aho_corasic_test5
驗證無匹配時的返回結果; - 簽名一致性測試:如
sig_check
驗證掩碼不同但實際匹配效果相同的簽名是否被視為相等。
If you need the complete source code, please add the WeChat number (c17865354792)
六、總結
二進制簽名查找器通過Aho-Corasick自動機實現了高效的多模式匹配,結合掩碼機制支持靈活的通配符處理,兼顧了效率、靈活性和易用性。其設計思路體現了“問題抽象→算法選型→工程實現→測試驗證”的完整流程,為二進制分析領域的模式識別任務提供了實用解決方案。
在實際應用中,這類工具不僅是逆向工程師的得力助手,也是惡意軟件檢測、二進制文件解析等領域的基礎組件,其核心思想(多模式匹配、通配符處理)對相關技術的學習和研發具有重要參考價值。
\Welcome to follow WeChat official account【程序猿編碼】