一种新的确定型有限自动机状态表示及压缩

针对传统DFA存在时间复杂度和空间复杂度高的问题,提出了一种新的DFA状态表示和字符-状态压缩方案。通过对传统DFA状态转换的观察发现,对于一个给定的输入来说,可以仅存储相邻状态之间的差异,从而得到一种新的DFA状态表示N-DFA;对每个大小不固定的状态设置一个状态指针来有效地减少每个指针所需要的比特数,从而得到一种基于输入字符的字符-状态压缩算法C-S;把N-DFA和C-S有效地集成在一起,进一步减少内存。实验结果表明,提出的N-DFA和C-S集成方案相比于传统的DFA和其他改进DFA方案,可以获得更好的内存压缩和加速性能。     

基于内容分析的协议识别研究

为解决多模式同时匹配的协议识别性能问题,提出了一种多模式组合有限状态机;以Thompson算法为基础,提出了一种压缩ε的NFA构造算法,该算法通过减少ε边及其对应状态,有效提高在协议模式编译时,NFA转换成DFA及DFA最小化过程的性能;基于上述理论与算法实现了一种One-Pass的组合多模式协议识别系统.实验表明:结合上述技术实现的系统,编译性能比标准DFA构造过程提高了7倍以上,匹配性能比L7-Filter提高了近20倍.     

软件测试中的路径划分技术

路径覆盖测试准则要优于其它已知的覆盖准则，但由于对一般的软件，路径数目太大，以至实际难以实现。路径划分是路径覆盖技术的一个折中方法。给定的程序Ｐ和给定模块的最大路径数目ｋ，按就近原则，现给出了一种划分Ｐ的算法，使得每个划分后的模块所包含的路径数目都少于等于ｋ。同时也给出了最佳划分的度量标准和最佳划分方法。