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

引言

几个月前，我遇到了一对奇怪的函数，它们似乎在用有限状态自动机验证输入。乍一看，我并没有意识到这实际上是在处理正则表达式，这也正是我花了相当长时间来理解这些例程的原因。你可能会问：“嗯，但正则表达式的字符串表示应该在二进制文件中，不是吗？“问题是它并不在。本文的目的是关注这种"编译"后的正则表达式，就像作者以某种方式将正则表达式转换为可直接在程序中使用的有限状态自动机（可能是为了效率）。要提取方便的字符串表示，你必须研究自动机。

在这篇短文中，我们将看到正则表达式在汇编/C语言中的样子，以及如何隐藏/混淆它。希望你喜欢阅读，并能在未来的逆向工程任务中识别编译的正则表达式，同时也能深度混淆你的正则表达式！

提取有限状态自动机

手动方式

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

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

注意：我刚刚有机会与Michal交谈，他说得完全正确，自动机并不完全是我们所说的正则表达式。以下是正则表达式应该匹配的示例：‘Hi-GARBAGEGARBAGE_Hi-1234’。我们不允许正则表达式在输入不匹配时回退状态到零。为了实现这一点，我们可以用"state = 0"语句替换返回语句。感谢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
68
69
70
71


#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

{% include_code regular_expressions_obfuscation_under_the_microscope/fsm_re2c_example.c %}

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

1

{% include_code regular_expressions_obfuscation_under_the_microscope/fsm_re2c_generated_non_optimized.c %}

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

手动生成

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

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

1

{% include_code regular_expressions_obfuscation_under_the_microscope/generate_c_fsm.py %}

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

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

更邪恶的想法：一个输入绑定所有黑暗中的正则表达式

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

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

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

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

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

玩弄自动机对你有好处。