AMP:一种关于程序控制流相似性比较的精确算法

程序的控制流,代表了程序的运行过程,也展现了程序员的编程思想,可以说是程序的基因。
对程序控制流进行相似度比较,可以有效地提取程序的本质特征,便于进行分类和聚类,因而广泛应用于各种大数据与人工智能处理领域之中。程序控制流是一种复杂的图结构,基于图结构的相似性比较有很多案例,但大多以高度降维牺牲精确度为代价,不适合用于对精确性要求极高的程序流程进行匹配。
本文综合了各种传统的图结构比较算法,分析了其优点与不足,提出了一种时空复杂度可控的精确比较算法(AMP算法),并将之应用于Android病毒检测领域,取得了一定的效果。

图结构相似度比较算法综述

图,是一种最复杂的基本数据结构。对于图结构的比较,学术界一直在做研究。但迄今为止,受限于复杂度与计算资源,在通用算法层面并未有很大的突破。相反,有一些问题已经被证明无法突破,如:图同构问题,即判断两图是否同构已经被认为是NP问题, 而子图同构问题即判断一图是否与另一图的子图同构已经被证明是NP-Compete问题。这给通过暴力搜索来精确匹配子图几乎判了死刑。
Algorithms on Trees and Graphs一书中,有详细讲解了图的相关算法和应用,如遍历问题,最大集问题,同构自构问题,子图问题等。作者均有详细的算法描述与代码实现,有兴趣者自行翻阅。
除此之外,学术界还有一些其他研究,侧重于解决效率问题。
总结一下,如果要想比较两图的相似度,大体上有如下3类主要方法:

精确比较

思想基于: 两图相似,仅当他们完全一致(图同构),或其一被另外包含(子图同构)。
这类属于暴力比较算法,主要涉及图同构,子图同构,最大共同子图等。有各种优化,如:
1.1 通过限制图的种类
X. Y. Jiang, H. BunkeIncluding: geometry in graph representations: A quadratic-time graph isomorphism algorithm and its applications
J. Hopcroft, J. Wong, Linear time algorithm for isomorphism of planar graphs
E. M. Luks, Isomorphism of Graphs of bounded valence can be tested in polynomial time
这类算法只是针对特定的图特定的应用场景优化,达到多项式时间解,但并未从根本解决图比较的复杂度问题。
1.2 通过精减搜索空间
典型的以回溯法为代表:
Ullmann:
J.R. Ullmann, An Algorithm for Subgraph Isomorphism
SD:
D.C. Schmidt, L.E. Druffel, A Fast Backtracking Algorithm to Test Directed Graphs for Isomorphism Using Distance Matrices
VF2:
L. P. Cordella, P. Foggia, C. Sansone, and M. Vento, An improved algorithm for matching large graphs.
L. P. Cordella, P. Foggia, C. Sansone, and M. Vento, A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs
Nauty:
B.D. McKay, Practical Graph Isomorphism
这类算法各有应用场合:
对于无规则的图, 如果足够稠密并且规模比较大,Nauty比较适合;如果很稀疏并且规模较小,VF2性能更好。 对于有一定规则的图,VF2性能较好,
但这些并未解决时间复杂度问题,最差情况下仍为指数或阶乘级。
python的graph-tool用的是VF2,空间复杂度为O(V),时间复杂度最好为O(V2), 最差为O(V!×V)。
1.3 面向集合比较
这类算法绕开一对一比较,考虑面向集合的比较,降低整体计算代价。算法时间复杂度是输入样本图大小的二次方并且与集合大小无关。
如:
H. Bunke, B.T. Messmer, Efficient Attributed Graph Matching and its Application toImage Analysis
但算法的空间复杂度却是集合大小的指数级,因此只能适用于小规模的计算。

特征抽取

思想基于:两图相似,很大程度上一些属性也相似, 如直径,特征值等。
算法通过抽取图的特征属性进行相似度计算,简化了问题的复杂度。
Sung-Hyuk Cha. Comprehensive survey on distance / similarity measures between probability density functions
显而易见,这是个取巧的方法,精确性有很大问题。

顶点迭代

思想基于:若各自邻节点相似,则两顶点相似;若所有顶点相似,则两图相似。
算法主要基于不动点计算,通过每一次迭代计算,在顶点之间交换或传播相似度分值,直到算法收敛。
想法有点借鉴与Pagerank

典型的如:
V. Blondel, A. Gajardo, M. Heymans, P. Senellart, and P. V. Dooren. A measure of similarity between graph vertices: Applications to synonym extraction and web searching

Sergey Melnik, Hector Garcia-Molina, and Erhard Rahm. Similarity flooding: A versatile graph matching algorithm and its application to schema matching

Glen Jeh and Jennifer Widom. SimRank: a measure of structural-context similarity

顶点、边结合评估:
L Zager and G Verghese. Graph similarity scoring and matching
置信传播:
Mohsen Bayati, David F. Gleich, Amin Saberi, and YingWang. Message passing algorithms for sparse network alignment

这类算法在时间复杂度上有明显提升,以SimRank为例,每次迭代最坏情况时间复杂度为 O(V3), 空间复杂度为O(V2), 适合大图计算。
这类方法本质上属于近似比较,以牺牲一定程度的精确性为代价的,不适合应用于严格拓扑结构比较,但在社交网络等非严格拓扑结构中却应用广泛,
因为对这类网络而言,相比较于结构的拓扑性,更关心结构的聚合性。
另外, 由于是近似比较,算法精确度的衡量也是个问题, Similarity flooding 就是靠人工来验证的。

以上3类方法中只有第一种属于精确比较,其他属于近似比较,在不同的场合有不同的应用。

Android程序控制流的特性

Android程序采用系统回调式设计,相比较传统的以Main为唯一入口点的程序有很大的不同。一个Android程序有很多入口点,如onCreate,onStart等。这就使得一个Android程序会有很多个不同子图,每个子图的起始点都不一样,但各个子图之间又可能会有连接,即出现子图相交的情况。因此,合理分割子图以平衡性能与精确度异常重要。此外,采用多线程或反射等隐式调用方法易导致调用关系在反编译后丢失,预处理程序需要能够处理这种情况,以确保最终的控制流图能最大程度表现程序的特征。

AMP算法

AMP(Align-Match-Prune)算法即对齐剪枝算法,是一种对特定的图结构,先降维成对应的生成树,再进行拓扑结构与节点相似度比较的算法。它不仅可以较精确地比较拓扑结构,还可以对节点的相似度进行比较,然后汇总判断。
AMP算法本质类似于 1.1,1.2的算法思想,针对程序控制流图的特性作了一些改进,算法的时间复杂度为 O(V3)。
算法过程如下:

1 original tree:
             T_1                               T_2
        _____v12_____                  ________w18_______________ 
       /             \                /         |                \
      v6              v11            w4       w12              ___w17___
     /               /   \          /  \      /  \            /    |    \
    v5             v9   v10       w1    w3  w5   w11         w13  w14 w16
   /  \            /  \                  |       /   \                  |
  v1  v4          v7  v8                w2      w9  w10                w15
     /  \                                      |
    v2  v3                                    w8
                                             /  \
                                            w6   w7


2 align to:
             T_1                               T_2
        _____v12_____                  ________w18_______________ 
       /             \                /         |                \
      v6              v11            w4       w12              ___w17___
     /               /   \          /  \      /  \            /    |    \
    v5             v9   v10       w1    w3  w5   w11         w13  w14 w16
   /  \            /  \                  |       /   \                  |
  v1  v4          v7  v8                w2      w9  w10                w15
     /  \                                      |
    v2  v3                                    w8

3 TDUMCST:
             T_1                               T_2
        ____(v12)____                  ______ (w18) _____________ 
       /             \                /         |                \
     (v6)            (v11)          (w4)       (w12)           __w17____
     /               /   \          /  \      /  \            /    |    \
   (v5)            (v9)  (v10)    (w1) (w3)  w5   (w11)      w13  w14  w16
   /  \            /  \                  |       /   \                  |
(v1)  (v4)       (v7)  v8              (w2)     (w9)  (w10)             w15
      /  \                                      |
    (v2)  v3                                   (w8)

4 prune to:
               T_1                     T_2                          
           ____(v12)____               (w18) _____________           
          /             \                |                \          
        (v6)            (v11)           (w12)           __w17____    
        /               /              /               /    |    \   
      (v5)            (v9)            w5              w13  w14  w16  
         \              \                                        |   
         (v4)            v8                                      w15 
           \                    
            v3                                                          


5 align to:
               T_1                 T_2                          
           ____(v12)____          (w18) _____________           
          /             \           |                \          
        (v6)            (v11)      (w12)           __w17____    
        /               /         /               /    |    \   
      (v5)            (v9)       w5              w13  w14  w16  
         \              \                                   |   
         (v4)            v8                                 w15  


6 prune to:


             T_1                     T_2                          
            (v12)____               (w18) _____________           
                     \                |                \          
                   (v11)             (w12)           __w17____    
                    /               /               /    |    \   
                  (v9)             w5              w13  w14  w16  
                     \                                        |   
                      v8                                      w15  

7 TDUMCST:
              T_1                     T_2                          
            (v12)____               (w18) _____________           
                     \                |                \          
                   (v11)             (w12)           __[w17]____    
                    /               /               /    |      \   
                  (v9)             w5              w13  w14   [w16]  
                     \                                         |   
                    (v8)                                     (w15)  

8 Involve v8 <-> w15, keep w16 

9 prune to:
             T_1                      T_2                              
            (v12)                   (w18) _____________               
                                      |                \              
                                     (w12)           __[w17]____      
                                    /               /    |      \     
                                   w5              w13  w14   [w16]   



10 align to:
           T_1                               T_2
         (v12)                              (w18)
11 done

output:
isomorphism subtree match1:   
            v12 <-> w18
            v6 <-> w12
            v11 <-> w4
            v5 <-> w11
            v9 <-> w3
            v10 <-> w1
            v1 <-> w10
            v4 <-> w9
            v7 <-> w2
            v2 <-> w8
isomorphism subtree match2: 
            v8 <->w15
"""                                      

虽然在降维成生成树的过程中有一定的信息损耗,但由于算法本身是基于最大同构子树设计,部分信息损耗不影响最终结果。另外,在基于API序列调用的流程图中,树的高度(即调用链的深度)其实有限,因此算法递归深度有限,在节点数可控的情况下,算法还是比较高效的。