正则表达式混淆技术深度解析

引言

几个月前，我遇到了一对奇怪的函数，它们通过有限状态自动机来验证输入。初看时并未意识到这实际上是在处理正则表达式，这也正是我花费大量时间理解这些例程的原因。你可能会问：“正则表达式的字符串表示应该存在于二进制文件中吧？“但事实并非如此。本文重点探讨这种"编译后"的正则表达式，即作者将正则表达式转换为可直接在程序中使用的有限状态机（可能是为了效率考虑）。要提取有用的字符串表示，就必须研究自动机。

在这篇短文中，我们将看到正则表达式在汇编/C语言中的表现形式，以及如何隐藏/混淆它。希望你能享受阅读，并在未来的逆向工程任务中既能识别编译后的正则表达式，又能有效地混淆自己的正则表达式！

提取有限状态机

手动方式

在自动化之前，先看看如何在C语言中实现简单的正则表达式。逆向工程总是更容易处理你至少曾经实现过的东西，即使实际实现与你所做的略有不同。

假设我们想要一个匹配"Hi-[0-9]{4}“的自动机。

注意：我与Michal交流后，他正确地指出这个自动机并不完全符合我们所说的正则表达式。以下是该正则表达式应该匹配的示例：‘Hi-GARBAGEGARBAGE_Hi-1234’。如果输入不匹配，我们不允许正则表达式回退状态到零。为了实现这一点，我们可以用"state = 0"语句替换return语句。感谢Michal的提醒。

从字符串表示中提取有限状态机后，我们可以得到以下自动机：

以下是该自动机的C语言实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67


#include <stdio.h>
#include <string.h>

unsigned char checkinput(char* s)
{
    unsigned int state = 0, i = 0;
    do
    {
        switch(state)
        {
            case 0:
            {
                if(*s == 'H')
                    state = 1;
                break;
            }

            case 1:
            {
                if(*s == 'i')
                    state = 2;
                else
                    return 0;
                break;
            }

            case 2:
            {
                if(*s == '-')
                    state = 3;
                else
                    return 0;
                break;
            }

            case 3 ... 6:
            {
                if(*s >= '0' && *s <= '9')
                    state++;
                else
                    return 0;
                break;
            }

            case 7:
                return 1;
        }
    } while(*s++);

    return 0;
}

int main(int argc, char *argv[])
{
    if(argc != 2)
    {
        printf("./fsm <string>\n");
        return 0;
    }

    if(checkinput(argv[1]))
        printf("Good boy.\n");
    else
        printf("Bad boy.\n");

    return 1;
}

测试程序执行：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


> fsm_example.exe garbage-Hi-1337-garbage
Good boy.

> fsm_example.exe garbage-Hi-1337
Good boy.

> fsm_example.exe Hi-1337-garbage
Good boy.

> fsm_example.exe Hi-dudies
Bad boy.

这个简单示例的目的是展示正则表达式字符串表示如何被编译成更难分析但更高效的形式（它不需要编译步骤，这就是为什么你可能会在实际软件中遇到这种东西）。即使代码初看起来很简单，但在汇编层面分析时，需要花费一些时间才能发现这只是一个简单的"Hi-[0-9]{4}“正则表达式。

在这类分析中，找到允许程序通过有限状态机不同节点的"状态"变量非常重要。然后，还需要弄清楚如何到达特定节点，以及从特定节点可到达的所有节点。简而言之，在分析结束时，你真正想要的是一个清晰的有限状态机，就像我们之前做的那样。一旦有了它，你就需要消除不可达节点，并最小化它以消除潜在的自动机混淆。

自动方式

但如果我们的正则表达式完全更复杂呢？手动实现有限状态机将是地狱般的任务。这就是为什么我想找到一些从正则表达式字符串操作生成自有有限状态机的方法。

使用re2c

re2c是一个很酷的简单工具，允许你在C注释中描述正则表达式，然后它将生成扫描器代码。作为示例，以下是生成先前正则表达式扫描器的源代码：

1

// 使用re2c生成扫描器代码示例

将源代码提供给re2c后，它会给你一个准备编译的扫描器：

1

// re2c生成的扫描器代码（非优化版本）

很酷不是吗？但事实上，如果你尝试编译并用Hexrays反编译（即使禁用优化），你会完全失望：它被简化得很厉害；对我们来说不太酷（但对逆向工程师来说很酷！）。

手动生成

这就是为什么我尝试自己生成扫描器的C代码。首先你需要一个"正则表达式字符串"到有限状态机的Python库：一种正则表达式编译器。然后，一旦你能够从正则表达式字符串生成有限状态机，你就可以完全自由地对自动机做任何你想做的事情。你可以混淆它，尝试优化它等等。你也可以自由生成你想要的C代码。

以下是我编写的用于生成先前使用的正则表达式扫描器的丑陋且有bug的PoC代码：

1

# 生成C语言有限状态机的Python代码

现在，如果你在IDA中打开它，控制流图将看起来像这样：

我猜逆向工程起来不会那么有趣。如果你足够好奇想看完整源代码，这里就是：fsm_generated_by_hand_example.c。

更邪恶的思路：用一个输入绑定所有正则表达式

请记住，先前的示例非常容易分析，即使我们必须在没有Hexrays的情况下在汇编级别进行分析（顺便说一句，Hexrays在简化汇编代码方面做得非常好，对我们来说很酷！）。即使我们用无用的状态/转换稍微混淆了自动机，我们可能还是想让事情变得更难。

一个困扰逆向工程师的有趣想法是使用多个正则表达式作为"输入过滤器”。你首先创建一个"宽松"的正则表达式，它有许多可能的有效输入。为了减少有效输入集，你使用另一个正则表达式作为过滤器。你这样做直到只剩下一个有效输入：你的序列号。注意，你可能还想构建复杂的正则表达式，因为你是邪恶的。

在这种情况下，逆向工程师必须分析所有不同的正则表达式。如果你专注于特定的正则表达式，你将会有太多的有效输入，而实际上只有一个能给你"好孩子"的结果（所有不同正则表达式的有效输入集的交集）。

如果你对这个主题感兴趣，我最近看到的一个很酷的资源是Michal Kowalczyk写的CTF任务报告：阅读它，非常棒。

更新：你还应该阅读@fdfalcon的后续文章"使用Pin对抗混淆正则表达式的黑盒方法”。使用Pin来击败有限状态机混淆，并证明我的混淆有点bug：一石二鸟:)）。

玩弄自动机对你有好处。