基于满十六叉有序树的程序行为建模搜索方法

程序行为建模及搜索是异常检测研究中的关键问题。本文提出利用系统调用发生时的程序计数器值对应的段号和段内偏移作为事件,将滑动窗口在有序事件上滑动得到事件序列集合,利用满十六叉有序树算法建立正常行为模型库。满十六叉有序树是为提高规则库的存储及搜索的效率而设计的,其存储的字节顺序隐含着结点间关系信息。在规则库中搜索某条规则的时间复杂度仅与树的深度有关,树的深度固定时的时间复杂度为O（1）。文中给出了满十六叉有序树的定义,分析了它的特点,并给出生成算法和搜索算法。

A Method for Program Behavior Modeling and Searching Based on Full 16-ary Ordered Trees

Program behavior modeling and searching is the key issue of anomaly detection. A method is presented, in which the segment ID and the offset of the program counter (PC),when system calls are invoked,are used as events.The event sequence set is produced by sliding the window in orderly events, and a normal behavior model set is built by using full 16-ary ordered trees.A full 16-ary ordered tree is designed for improving the efficiency of storing and searching rule sets.The storage byte sequence in the full 16-ary ordered tree implies the relationship information between nodes. The time complexity of searching the rule set for a rule only relates to the depth of the tree, and if the depth of the tree is fixed, the time complexity is O(1). The definition of a full 16-ary ordered tree, its features,its creating and searching algorithms are presented.