二进制签名查找器（Aho-Corasick 自动机）：设计思路与实现原理(C/C++代码实现)

发布于：2025-08-07 ⋅ 阅读:(16) ⋅ 点赞:(0)

在逆向工程、恶意软件分析和二进制文件解析领域，快速准确地识别特定字节模式（即“签名”）是一项核心任务。本文将围绕一款基于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【程序猿编码】

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布