FSMEFSM的被动测试算法及其在BGPOSPF协议测试的实现.ppt

1、FSM/EFSM的被动测试算法及其在BGP/OSPF协议测试的实现,主要内容,选题背景 完成的主要工作 被动测试系统结构 EFSM被动测试变量管理的算法研究 EFSM被动测试变量管理器的实现 易于移植的Watcher结构 未来工作展望,选题背景,1972年：被动测试被提出但没有有效算法 1997年：D. Lee提出FSM/NFSM模型的被动测试算法 1998年：R. Miller提出CFSM模型的被动测试算法 EFSM模型的被动测试算法？ 用于实际协议测试的算法？,完成的主要工作,算法：EFSM被动测试算法中的变量管理 实现： FSM模型描述BGP协议的被动测试器 NFSM/EFSM模型描述O

2、SPF的被动测试器 实验： 模拟协议实现（学习NS2/Socrates） 数据收集（BW的修改，OW） 数据的处理（BGP/OSPF的包解析器等）,FSM被动测试系统结构,EFSM被动测试系统结构,EFSM被动测试的变量管理,现有的方案： NFSM 不考虑变量的问题 测试能力? 区域状态机的思路 EFSM(变量区间状态)FSM 如何记录可能的状态? 放弃不确定的变量值Tabour99 不分裂状态，放弃记录有多个可能取值的变量,EFSM被动测试的变量管理,提出的方案： 用区间记录可能的取值 “区域自动机”“放弃不确定值”的折衷方案 利用条件获取信息 发生了变迁条件为(x=c)的变迁x=c 有限度

3、地分裂节点（陈东洛） situation =状态+变量值； 可能的situation过多时，把状态相同的situation合并。 记录历史信息（陈东洛） 不确定变迁条件+不确定动作=assertion(断言) situation=状态+变量值+assertion (断言),EFSM被动测试的变量管理,四个方案的综合： 兼容性 报错条件可以漏过一些错误，不能误判 每个算法都是遵守被动测试报错条件的，算法的组合仍然满足报错条件。 冗余性 可能值区间 vs 记录历史信息 历史信息记录的是可能值区间不能记录确定的信息,EFSM被动测试的综合算法,状态控制器算法： 数据结构：一个situation队列A

4、，一个situation包括了一组变量值和被测实现当前处在的协议自动机状态。 1、 等待一个事件；读入一个事件 2、 建立一个空的situation队列B（新生成的situation列表） 3、 对队列A里面每一个situation S做： 对从S发出的每一条满足事件的变迁（输入输出与事件一致）做： A、 复制一个新的situation S，S=S。 B、 以S为situation，调用变量管理器的transition函数，判断变迁条件是否可满足 C、 如果变迁条件满足，则把S加入到队列B中，否则删除S。 5、 清空队列A，把队列B的situation都加入到队列A里面，删除队列B，转1,EF

5、SM被动测试的综合算法,变量管理器算法：,EFSM被动测试变量管理器的实现,变量管理器框架：,EFSM被动测试变量管理器的实现,可能值区间Value类的数据结构： private: ELEMENT_TYPE upper, lower;/取值区间的上确界和下确界 bool error;/是否在运算中发生错误 （用于错误传播的控制） public: bool changed;/是否在运算中改变了区间（用于从条件获取信息的传播） 基于Value定义的运算规则,EFSM被动测试变量管理器的实现,变迁条件的描述： 析取范式 从条件中获取变量值：Implication Actions,EFSM被动测试变量

6、管理器的实现,Assertion的描述： 合取范式 和取范式有利于做Assertion去冗余处理： 判断和取范式中每一个合取项，如果能被变量值确定的描述，则该合取项为冗余信息。,EFSM被动测试变量管理器的实现,条件的描述：,EFSM被动测试变量管理器的实现,表达式的描述：,EFSM被动测试变量管理器的实现,Action的分析过程：,易于移植的Watcher结构,历史： BGP Watcher BGP Watcher for Passive Testing OSPF Watcher for Passive Testing Protocol Watcher结构,OSPF Watcher,Prot

7、ocol Watcher,Protocol Watcher,对于一个新的协议，需要重新设计的模块有： l根据协议设计数据包的数据结构、文件结构和缓冲结构 l根据新的文件结构、缓冲结构重新设计文件和缓冲的初始化模块和结束模块 l重新设计事件处理器模块 l重新设计各层的过滤器（其实大多数过滤器是不需要的，直接返回允许通过即可） l可选：重新设计可视化模块,Protocol Watcher,接口模块设计规范： 初始化模块 Int event_handler_init(void) 包处理模块 Int event_handler_process(char* buf, int len) 完成模块 Int event_handler_done(void) MAC层过滤模块 int ProtocolFilter(char *buf,int len),未来工作展望,在理论上对现有的EFSM变量管理算法进行复杂性分析，提高算法效率。 在EFSM模