布尔逻辑决策树到有限状态机的转换

在分析网络安全事件时，检测算法根据布尔表达式评估属性，以确定事件是否属于类。本文介绍如何将布尔表达式转换为有限状态机，以实现更简单、高性能的计算。

开源项目CyberProbe就是这种实现的特色。在Python中实现了规则到有限状态机(FSM)的转换和FSM形式规则的应用。CyberProbe支持使用数百万条规则，这些规则可以在单个处理器内核上以超过200k事件/秒的速度应用。

将布尔逻辑标准应用于事件解决了许多扫描和检测问题。例如，在与受保护服务的交互中生成的事件。该事件具有以下属性：

我尝试检测的对象类的一个或多个布尔表达式：

如果TCP端口号是80或8080，IP地址是10.0.0.1，url是http://www.example.com/malware.dat或http://example.com/malware.dat…。

其目的是对照大量布尔表达式分析此类事件的高速率流，以对事件进行分类。

布尔表达式由、和(…)的组合组成。，或(…)。而不是(…)。函数以及类型：值匹配术语。我使用type：value对作为匹配项，因为这在我工作的域中很有用，但是我们也可以很容易地使用字符串。

使用type：value对输入对布尔表达式求值的一种简单方法是将布尔表达式表示为树，然后使用type：value对触发求值。观测值存储在树中。

对于每个type：value属性，查看布尔树中是否有对应的type：value术语。如果存在，则将术语节点设置为true，并计算父节点。

计算父节点或节点时，如果任意子节点为TRUE，则OR节点为TRUE，并计算其父节点。

在计算父节点和节点时，如果所有子节点都为True，则And节点为True，并计算其父节点。

计算父NOT节点时，如果子节点为TRUE，则NOT节点为FALSE。一旦完成了所有属性的计算，如果Not节点由于其子节点为False而没有被认为是False，则它的计算结果为True，并且它的父节点的计算结果为True。

这是一个简单的算法；本文的重点是提供优化。

这里有一个折衷方案，将布尔树转换为FSM的算法是计算密集型的：它具有与节点数量非线性的复杂性：它与组合节点(如下所述)和类型：值项的乘积呈线性关系。在现实场景中，当解析规则时，布尔表达式将被转换为FSM，此后可以多次使用FSM。

为了找到FSM，我们在布尔树中查找在评估进行时需要观察状态的所有节点。如果您查看上面的示例，您可以看到or节点和and节点是不同的。当或节点的子节点评估为TRUE时，立即导致其父节点为TRUE，因此不需要保留有关或节点的子节点的状态。而当AND节点的子节点为TRUE时，这可能需要存储以供以后评估，以确定AND节点可以被评估为TRUE的点。

NOT节点的求值也很复杂：由于NOT节点的子节点在分析期间保持错误求值，因此可以将其求值为TRUE。

我们在这里声明的规则是，布尔树中的一些节点可以描述为基本状态：

树的根本质上是命中状态，这意味着布尔表达式为真。这是一个基本状态。

AND节点的子节点是基本状态，除非它是NOT节点。

NOT节点的子节点是基本状态，除非它本身是NOT节点。

在上面的示例中，基本状态是两个或节点和IP：10.0.0.1节点。根据规则3，所有人都有资格。

该实现为每个州提供一个州名称，该名称由字母s加上唯一数字组成，以深度优先遍历方式分配。具有状态的示例布尔树如下所示；和节点的三个子节点被赋予状态，父节点和节点表示命中状态。

基本状态是需要记录部分状态的节点。FSM中的一个节点同时表示所有状态，即所有有效的基本状态组合。因此，组合状态集合由基本状态的所有组合组成。这包括空集和所有州的联合。

组合状态需要有一个状态名称：在我的实现中，我通过排序将状态组合到一个名称中，在名称之前使用连字符分隔状态编号。例如，状态s4、s7、s13的组合称为s4-7-13。

空集有一个特殊的名称，我们称之为init。它表示不知道信息的FSM的初始状态。

有一个特殊的状态命中，它用于描述基本状态的任何组合，包括根节点求值为真。忽略其他状态的组合。

这一步本质上是要计算出所有类型：值匹配节点对所有组合状态执行的操作。有一个特殊的匹配术语End：，它用于评估当术语列表完成时NOT节点会发生什么情况。

对于每个组合状态：计算出每个匹配项的输入组合状态的州名称：给定输入状态，将该项求值为TRUE会产生什么状态？计算出输出组合状态的状态名称。在给定输入状态的情况下，记录转换(输入、匹配项、输出)。将end：求值为true会产生什么状态？计算出输出组合状态记录转换(输入、结束：、输出)的状态名称。

对于此分析，当整个布尔表达式的计算结果为TRUE(即布尔表达式的根节点为TRUE)时，我们将为其指定一个特殊的名称HIT。

结果是一组完整的三元组：(输入、术语、输出)。如果输入和输出状态相同，我们可以忽略转换，以便有限状态机只包含改变状态的边。

在这一点上，FSM具有一些低效：FSM的某些区域可能无法从init导航到。这将在下一步中解决。

并不是所有的组合状态都可以从init中达到，因此发现的一些转换可以被视为不相关而丢弃。

迭代FSM，添加可以导航到集合中任何状态的所有转换。

在这一点上，我们知道所有可能导致撞击的状态。然而，会有一些转变导致不在这个集合中的状态，因此永远不能旅行去命中。因此，对无效转换的第一个简化是将所有转换到不在此集合中的状态减少到名为FAIL的单个状态。

FSM还有第二个简化：有些状态不能从init导航，可以删除：

迭代FSM，查找可以从集合中的任何状态导航的所有转换。

在这一点上，我们知道密克罗尼西亚联邦哪些区域是无法到达的，它们可以被移除。

上述二叉树的FSM如下所示。初始化状态表示初始FSM状态。命中状态表示布尔表达式的成功求值为TRUE。我们已经提到了失败状态，该状态仅在使用NOT表达式时才会发生，而NOT表达式不会作为如上所述的布尔表达式的结果出现。请参见下面的示例。

在发现属性时，将type：值与当前状态的转换进行比较。如果存在转换，则FSM将移动到新状态。

当达到命中状态时，这相当于布尔表达式求值为TRUE。

当达到失败状态时，不需要进一步的属性发现，并且评估可以快速失败。

对于每个术语需要单个FSM查找这一事实意味着该方法具有性能优势。

在删除无效转换和发现失败状态之前查看此图表非常有趣。一些示例工件：

不存在到仅由状态S9组成的组合状态的转换。这是因为在不将S5和S8都评估为真的情况下不可能达到该状态。有从S9到HIT的转换，但是没有通向S9状态的路径，所以它们永远不会被采用。

状态S5-8同样无效，如果S5和S8被评估为真，则S9也为真。在这两种情况下，此条件的有效状态都是S5-8-9。这导致具有两个节点的FSM的不可达部分未与FSM的其余部分连接。

S3为真的任何状态都不会导致命中，因为根和节点必然为假。包括S3的所有节点都可以由故障状态替换。

删除无效转换并映射到故障状态后，FSM更容易理解：

此示例说明了失败状态：一旦转换导致此状态，则进一步的信息不可能允许转换到命中状态。发现TCP：8081或TCP：8082处于任何状态都会导致转换到失败状态。根据您的分析策略，失败状态可能很有用：它可能是快速失败的点，也可能是进一步评估的捷径。此示例还说明了导致命中的特殊end：term。

由于所有的和条件，此示例需要保留更多的状态。

AND(or(url：http://www.example.com/malware.dat，url：http://example.com/malware.dat)，ipv4：10.0.0.1，not(or(or(tcp：8081，tcp：8082)，ipv4：10.0.0.2))。

FSM模型使用一大组规则进行高性能扫描，每个规则都使用上述方法转换为FSM。虽然理论上可以从单个FSM产生超级FSM，但FSM的大小很快就会变得笨拙。因为对于贡献FSM集合中的每个状态组合，在UBER-FSM中需要有单个状态。

一种简单的评估方法是标识一组启动器，该组启动器是从每个FSM中的初始化状态引出的一组术语。如果在分析属性时检测到任何发起者，则激活相应的FSM并将其放在正被跟踪的FSM集合上，以便在随后的匹配项评估中进行状态改变。此方法减少了需要跟踪的FSM数量。我发现在实践中，这导致了一小组用于评估的FSM。

使用此方法，不适合快速故障FSM并将其从跟踪的FSM集中删除；必须跟踪FSM至故障状态，以防止FSM随后重新激活。

CyberProbe项目包括一种以JSON格式编写规则的方法。有许多实用程序可以解析规则格式并输出FSM信息，例如Indicators-Show-FSM获取规则/指示器文件并转储文件中每个规则的FSM。这是以人类可读的形式输出的，显示状态转换：

[指示器]$Indicators-show-fsm case1.json 3ce77704-abe4-4527-84e6-ed6a745aebcf：提供恶意软件服务的页面的url init-tcp：8080->；s6 init-tcp：80->；s6 init-url：http://example.org/malware.dat->；s3 init-url：http://www.example.org/malware.dat->；s3 s3-tcp：8080->；命中s3-。点击s6-url：http://www.example.org/malware.dat->；点击。

Indicators-graph-fsm是一个实用程序，它获取规则/指示器文件和规则ID，并输出描述FSM的Graphviz格式的图形，这就是我如何生成本文中的图表的：

[指示器]$Indicators-graph-FSM case1.json\3ce77704-abe4-4527-84e6-ed6a745aebcf>；raph.dot[指示器]$dot-Tpng raph.dot>；raph.png。

Indicators-Dump-FSM是一个实用程序，它获取指示器文件并以JSON形式输出FSM。

#！/usr/bin/env python3 import sys import Cyberprobe.fsm_Extract as FSME from Cyberprobe.logictree import and，or，not，Match expression=and([or([Match("；TCP"；，"；80"；)，Match("；TCP"；，"；8080"；)])，Match("；IPv4"；，"；)，或者([Match("；url"；，"；http://www.example.com/malware.dat"；)，Match("；url"；，"；http：/example.com/malware.dat"；)])]])])fsm=fsme.Extract(表达式)#为fsm中的v转储fsm：for w in v[1]：打印("；%s--%s：%s->；%s"；%(v[0]，w[0]，w[1]，v[2])。

为了对我的算法进行基准测试，我比较了FSM方法和上面“基本算法”中讨论的基本布尔树算法的性能，这两种算法都是用Python编写的。下图显示了作为x轴使用的规则数，以及作为y轴的事件处理率。这是一种显示正在使用的规则数量如何影响事件吞吐量的方法。橙色线条代表FSM的表现。您可以看到，正在使用的规则数量对算法吞吐量的影响非常小。请注意x轴上的对数刻度。

这是在我的旧MacBook上的VirtualBox上运行的，例如，期望云VM具有更好的性能。

这是对性能的一个非常快速的介绍，也许我稍后会做一篇关于性能的后续文章。