数学课上打盹的时候想出来的，一种在反病毒领域可能会有奇效的PrefixSpan有向图变种算法，可以达到线性级别的复杂度，目前应用在CSafe-Starlight V3系列引擎的tosSPM语义解析引擎上。引擎的分析能力似乎还不错，也算是有数据证明了这个猜想是成立的吧。
事情起源于CSafe-Starlight V3系列反病毒引擎的研发工作。
v3系列引擎的架构，我大概从上学期期末之前就开始设计了。最初的想法是提取程序的外部调用森林，即对程序进行线性反汇编和简单的跳转模拟，对程序的每个入口点向下延伸出的所有可达的导出函数调用进行分析，然后解析出一个拥有多个入口点，也就是多个根节点的外部调用森林，在这个森林上执行带跳过（是为了规避混淆）的频繁调用链挖掘（由于目标数据结构是森林，因此设计一个带混淆跳过的树上运行的频繁序列挖掘算法并非难事，我当时自己写了一版设计，后来发现和PrefixSpan是同一个原理），然后对挖掘出的频繁恶意/良性调用链建立数据库，推理的时候再进行匹配与加权。
这个时候，想必接触过程序外部调用流图，也就是EFG（External Flow Graph）的同学应该看出来了，这套想法是相当天真稚嫩且不可靠的。核心原因在于一点——对于一个反汇编后的PE程序，其外部调用之间的关系是非常复杂的，要将一个程序的所有可能的跳转树全部展开，在外部调用森林生成部分，程序就会卡死（结合后文就很容易发现，这本质上是一个将有向图带去重地强制展开为树状结构的想法，而解决这个问题的算法时间复杂度是指数级别的）。
其实初版设计的结局也是不难想到的~毕竟，如果真的可以让我就这么轻易地在有限的时间复杂度内，从那么庞大的程序样本库中提取出准确的频繁调用链来（至少在我看来，调用链算是一个特别有用的静态分析特征了），那肯定早就有相关的研究和实践了。
怎么办呢？ternaryop8479也想不到其他办法，那就只能抛弃这个思路，硬着头皮使用EFG了。
不过~在有向图（EFG外部调用流图本质上其实就是一个有向图）上执行（带去重的）频繁链条挖掘属于NP难问题，同样是一个难以在有限时间复杂度内完成的任务。不过我们可以通过启发式算法优化，在尽可能地保留信息的情况下，尝试将这个挖掘算法优化到我们可以接受、甚至能够接近线性级别的复杂程度，而这就是接下来我们这篇文章要讲的内容了。
这个时候，有认真读文章以及前言的同学应该看出来了，一个用来在线性数据结构上执行频繁序列匹配的PrefixSpan算法，怎么会被我拿来放到EFG上运行呢？PrefixSpan算法，又是怎么在一个有向图上跑起来的呢？
这里就不得不提到PrefixSpan算法的一个概念——"投影"。
PrefixSpan算法，本质上其实就是一个dfs（当然，PrefixSpan实际上不止可以用dfs实现，还有很多种方法可以实现这个算法，但考虑到我们不是教科书，这里就不细讲了），而dfs过程中每一步的状态，就是当前深度下的投影数据库，而dfs向下递归的步骤，就是扩展投影前缀的操作。而让PrefixSpan算法在有向图上运行的精髓，就在于在有向图变种算法中，扩展投影前缀的操作不再是向后移动一位序列指针，而是从当前节点出发，遍历所有出边指向的后继节点（实际算法实现中还应该有防环处理，这里省略掉这个步骤）。
此外，PrefixSpan算法还具备一个哈希等算法不具备的优点——那就是它天然容易实现节点跳过机制。
我们都知道，在实际运行环境中，一个程序的EFG可以是非常复杂的，而且对于狡猾的攻击者来说，他们执行恶意操作的时候，很有可能不是一气呵成，而是在恶意执行链中插入了很多的伪装API，来增加我们分析的复杂度。所以，让我们最后产出的挖掘算法具备节点跳跃的机制，是非常有必要的。
那么，PrefixSpan算法是如何自然地实现这个节点跳过机制的呢？核心还是"投影"这个概念。
说到这里，想必学习过PrefixSpan算法的同学已经能够想到应该怎么做了。还是对"扩展投影前缀"的操作下手，我们现在扩展投影前缀，不再是"从当前节点出发，遍历所有出边指向的后继节点"，而是以当前节点作为起点，执行有限深度的bfs（你要愿意也可以用dfs，但是嘛……嵌套递归，法力无边，不是我等贱民能够驾驭的）算法，把所有在指定步数范围内可达的后继节点都纳入候选集合，这样，扩展出的投影数据库中就天然拥有了当前节点的下个、下下个、甚至是下下下个节点的数据，自然就可以进行带跳过的挖掘。
到这里，我们就已经讲清楚，一个PrefixSpan算法，是为何会被我拿到反病毒领域进行应用、如何能在一个有向图上运行的了。如果读者还有不太清楚的地方，可以查阅引擎源码，引擎的代码里都有详细的注释，或许可以帮助理解（给个star叭求求了QAQ）。
不过到此为止，我们所讲解的都是如何让PrefixSpan在EFG上运行起来，但"理论可行"不等于"实践可行"，横在我们面前的还有最后一道门槛——那就是PrefixSpan算法的时间复杂度。一个标准的基于有向图运行的PrefixSpan变种算法，其最坏时间复杂度为O(ΣV * d^L)（其中V代表图平均节点数，ΣV为所有图的节点数之和，d代表图的平均出度，L代表最大链条深度），当L较大（一般设计为3~5，也就是时间复杂度为3次方~5次方）。尽管我们可以通过最小支持度等剪枝手段降低这种标准算法的复杂度，但仍然无法影响到最坏时间复杂度，或抑制住大规模数据集下的组合爆炸问题。
那么，就没有一种合适的启发式算法，能够让我们在大规模EFG数据集上，高效地执行频繁API调用链挖掘吗？
当然有！不然我写这篇博客干嘛。不但有，而且非常简单，只需要在基于有向图的PrefixSpan朴素变种算法的基础上引入一个参数就够了——"最大扩张率"（Maximum Expansion Ratio），记作Re。而这个参数的定义也非常简洁直观：
其中C代表本次递归调用中，从当前前缀扩展出的合法候选API集合，P代表当前前缀投影集。
当我们引入这个参数之后，就可以很容易证明，基于该参数的变种PrefixSpan算法（我将其命名为tosSpan！）可以达到近线性级别的复杂度，如下。
首先，明确代码的执行结构，也就是简化地写出tosSpan算法的伪代码。定义dfs(P, depth)对投影集P执行递归搜索，其中S代表最大跳过数，R_e即Re：
dfs(P, depth):
对 P 中每个投影做受限 BFS（深度 ≤ S+1）:
收集后继API到候选投影集
执行其他参数的剪枝筛选
若 |C|（|C|可以直接读取候选投影集得到） > |P|·R_e: return // 膨胀率剪枝
遍历候选投影集的后继API（每个API持有一个投影集，记为P'）:
push 前缀，记录调用链
若 depth+1 < L: dfs(P', depth+1)
pop 前缀
遍历EFG集合中所有EFG的所有节点:
将当前API加入到1-gram候选投影集
遍历1-gram候选投影集（每个API持有一个投影集，记为P'）:
执行其他参数的剪枝筛选
dfs(P', 0)我们首先对dfs(P, depth)的时间复杂度进行分析。
单层调用成本
遍历投影集P，其中每个投影属于某一张EFG。对每个投影所属的图执行一次受限bfs：
bfs深度限制为S+1，每层遍历其子节点，
评论