『杂项』数据溯源与验真的探索之路（2）

点击蓝字关注我们

0x00 前言

数据溯源与验真类题目中正则匹配是其中的重要部分，面对庞大的数据量，如何提高正则匹配的效率是一个值得思考的问题。使用高效的正则表达式引擎可以显著提高效率。

0x01 RE2

1.1 介绍

RE2是Google开发的一个正则表达式库，它的设计目标是提供高性能、安全的正则表达式匹配功能。与其他正则表达式库不同，RE2不支持一些常见但危险的正则表达式语法，如回溯引用和无限重复等。这种限制使得RE2可以提供更可靠的正则表达式匹配，并防止正则表达式的恶意使用。同时，RE2采用了一种高效的正则表达式匹配算法，能够处理极大的输入数据，并在时间和空间上都有良好的性能表现。

1.2 安装

安装过程可参考github官方文档。无论将其与哪种编程语言进行绑定都需要先安装re2。

git clone https://code.googlesource.com/re2cd re2makemake testmake installmake testinstall

MacOS可使用homebrew进行安装，若要与python绑定还需安装pybind11。

brew install -s re2 pybind11

如果要将其与python进行绑定，可安装pyre2库。

pip install pyre2

1.3 应用

为了方便使用，安装pyre2将re2与python绑定，以下列脚本为例。

import osimport re2 as reimport timestart = time.perf_counter()# 正则表达式email_pattern = re.compile(r'b(((([*+-=?^_{|}~w])|([*+-=?^_{|}~w][*+-=?^_{|}~.w]{0,}[*+-=?^_{|}~w]))[@]w+([-.]w+)*.[A-Za-z]{2,8}))b')'''b：表示单词边界，用于确保匹配的是完整的邮箱地址。(：开始一个捕获组。((([+-=?^_{|}~w])|([+-=?^{|}~w][*+-=?^{|}~.w]{0,}[*+-=?^{|}~w]))：表示邮箱地址的本地部分，可以是一个字母、数字或者特殊字符，也可以包含多个字母、数字、点号（.）或下划线（），但是必须以字母或数字结尾。[@]：表示必须包含一个@符号。w+：表示@符号后面的域名部分，必须是一个或多个字母、数字或下划线。([-.]w+)*：表示域名中可能包含一个或多个连字符（-）或点号（.），后面跟着一个或多个字母、数字或下划线的字符串。.[A-Za-z]{2,8}：表示域名的最后一部分，必须是一个点号后面跟着两个到八个字母的字符串，比如.com、.edu等等。)：结束捕获组。b：单词边界。'''# 遍历指定文件夹下的所有txt文件folder_path = 'folder/txt_files'output_file = 'email.txt'with open(output_file, 'w') as f:    for file_name in os.listdir(folder_path):        if file_name.endswith('.txt'):            file_path = os.path.join(folder_path, file_name)            with open(file_path, 'r') as txt_file:                # 对txt文件中的每一行进行匹配                for line in txt_file:                    result = [m.group(0) for m in email_pattern.finditer(line)]                    # 如果匹配到了银行卡号，将结果按照指定格式写入到txt文件中                    if result:                        for eamil in result:                            f.write('{} {} {}n'.format(file_name, 'email', eamil))end = time.perf_counter()spt = end - startprint('完成，用时{}秒'.format(spt))

使用pyre2来代替python自带的re，效率可以提升至原来的三倍，但需要注意的是，由于RE2是一个C++库，其设计目标是保证正则表达式的处理，提高效率，节约内存和时间。为了实现这一目标，RE2在正则语法上有一些限制，不如不支持回溯、条件正则表达式等。所以，使用RE2时要注意对正则表达式进行一定的修改。

0x02 HyperScan

2.1 介绍

Hyperscan是由Intel推出的一种高性能的正则表达式引擎，特别适用于高吞吐量和低延迟的应用程序。它使用多核和硬件加速技术，能够快速匹配大量的正则表达式。它可用于许多应用程序，如网络安全、网络监控和日志分析等。Hyperscan可以满足高速、高效的文本模式匹配的需求。

HyperScan使用预编译的方法将正则表达式和匹配模式、平台信息等编译为一个数据库。

将待匹配内容的数据块和数据库以及分配的内存空间共同参与了HyperScan的运行，运行结束后使用Callback函数来返回匹配内容。

2.2 安装

Hyperscan的安装可参考官方github。

MacOS安装可直接使用homebrew。

brew install hyperscan

HyperScan在5.0版本之后开始对Windows平台全面支持。安装过程中应注意以下几点。

需下载指定版本的Boost源码，并将其解压到HyperScan目录下。
如果要将HyperScan与python绑定，下载PCRE-8.45源码并解压到HyperScan目录下。
下载sqlite-amalgamation源码解压到HyperScan目录后要修改文件夹名为sqlite3
编译安装Ragel可能会出现大大小小的问题，可以考虑下载编译完成后的。

2.3 应用

HyperScan最具有特色的用法当属多模式匹配。不同于别的正则表达式引擎，HyperScan可以将多个正则表达式编译到database中，经过一次匹配即可得到所有正则表达式的匹配结果。

#include <hs/hs.h>#include <stdio.h>#include <stdlib.h>#include <string.h>#include <pthread.h>#define MAX_PATTERNS 10#define THREADS 4// 定义正则表达式和对应的回调函数const char *patterns[MAX_PATTERNS] = {    "test[0-9]+",    "hello[0-9]+",    "world[0-9]+",    "foo[0-9]+",    "bar[0-9]+",    "baz[0-9]+",    "alpha[0-9]+",    "beta[0-9]+",    "gamma[0-9]+",    "delta[0-9]+"};int ids[MAX_PATTERNS];hs_database_t *db = NULL;hs_scratch_t **scratch = NULL;pthread_t threads[THREADS];pthread_mutex_t mutex;int done = 0;// 定义回调函数，用于匹配到正则表达式时的处理static int eventHandler(unsigned int id, unsigned long long from,                        unsigned long long to, unsigned int flags,                        void *context){    printf("Match for pattern ID %u from position %llu to %llun", id, from, to);    return 0;}// 定义线程函数，用于匹配正则表达式void *matchThread(void *arg){    int threadNum = *((int *) arg);    unsigned int start = threadNum * MAX_PATTERNS / THREADS;    unsigned int end = (threadNum + 1) * MAX_PATTERNS / THREADS;    // 分配内存    if (hs_alloc_scratch(db, &scratch[threadNum]) != HS_SUCCESS) {        fprintf(stderr, "Error allocating scratch spacen");        return NULL;    }    // 匹配正则表达式    if (hs_scan_multi(db, (const char **)patterns, ids, start, end - start,                      0, scratch[threadNum], eventHandler, NULL) != HS_SUCCESS) {        fprintf(stderr, "Error scanning datan");        return NULL;    }    // 释放内存    hs_free_scratch(scratch[threadNum]);    // 通知主线程已完成    pthread_mutex_lock(&mutex);    done++;    pthread_mutex_unlock(&mutex);    return NULL;}int main(int argc, char **argv){    hs_compile_error_t *compile_err = NULL;    int i;    // 初始化互斥锁    pthread_mutex_init(&mutex, NULL);    // 编译正则表达式    if (hs_compile_multi(patterns, 0, HS_MODE_BLOCK, NULL, ids, MAX_PATTERNS, &db, &compile_err) != HS_SUCCESS) {        fprintf(stderr, "Error compiling regex: %sn", compile_err->message);        hs_free_compile_error(compile_err);        return -1;    }    // 分配内存    scratch = (hs_scratch_t **)malloc(sizeof(hs_scratch_t *) * THREADS);    if (scratch == NULL) {        fprintf(stderr, "Error allocating memoryn");        hs_free_database(db);        return -1;    }    // 创建线程  for (i = 0; i < THREADS; i++) {    int *arg = (int *) malloc(sizeof(int));    *arg = i;    pthread_create(&threads[i], NULL, matchThread, arg);}// 等待所有线程完成while (done < THREADS) {    usleep(1000);}// 释放内存for (i = 0; i < THREADS; i++) {    pthread_join(threads[i], NULL);}free(scratch);hs_free_database(db);// 销毁互斥锁pthread_mutex_destroy(&mutex);return 0;}