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

FSM EFSM的被动测试算法及其在BGP OSPF协议测试的实现 答辩人 魏小亮指导教师 吴建平教授2001年6月 主要内容 选题背景完成的主要工作被动测试系统结构EFSM被动测试变量管理的算法研究EFSM被动测试变量管理器的实现易于移植的Watcher结构未来工作展望 选题背景 1972年 被动测试被提出但没有有效算法1997年 D Lee提出FSM NFSM模型的被动测试算法1998年 R Miller提出CFSM模型的被动测试算法EFSM模型的被动测试算法 用于实际协议测试的算法 完成的主要工作 算法 EFSM被动测试算法中的变量管理实现 FSM模型描述BGP协议的被动测试器NFSM EFSM模型描述OSPF的被动测试器实验 模拟协议实现 学习NS2 Socrates 数据收集 BW的修改 OW 数据的处理 BGP OSPF的包解析器等 FSM被动测试系统结构 EFSM被动测试系统结构 EFSM被动测试的变量管理 现有的方案 NFSM不考虑变量的问题测试能力 区域状态机的思路EFSM 变量区间 状态 FSM如何记录可能的状态 放弃不确定的变量值 Tabour99 不分裂状态 放弃记录有多个可能取值的变量 EFSM被动测试的变量管理 提出的方案 用区间记录可能的取值 区域自动机 放弃不确定值 的折衷方案利用条件获取信息发生了变迁条件为 x c 的变迁 x c有限度地分裂节点 陈东洛 situation 状态 变量值 可能的situation过多时 把状态相同的situation合并 记录历史信息 陈东洛 不确定变迁条件 不确定动作 assertion 断言 situation 状态 变量值 assertion 断言 EFSM被动测试的变量管理 四个方案的综合 兼容性报错条件 可以漏过一些错误 不能误判每个算法都是遵守被动测试报错条件的 算法的组合仍然满足报错条件 冗余性可能值区间vs记录历史信息历史信息记录的是可能值区间不能记录确定的信息 EFSM被动测试的综合算法 状态控制器算法 数据结构 一个situation队列A 一个situation包括了一组变量值和被测实现当前处在的协议自动机状态 1 等待一个事件 读入一个事件2 建立一个空的situation队列B 新生成的situation列表 3 对队列A里面每一个situationS做 对从S发出的每一条满足事件的变迁 输入输出与事件一致 做 A 复制一个新的situationS S S B 以S 为situation 调用变量管理器的transition函数 判断变迁条件是否可满足C 如果变迁条件满足 则把S 加入到队列B中 否则删除S 5 清空队列A 把队列B的situation都加入到队列A里面 删除队列B 转1 EFSM被动测试的综合算法 变量管理器算法 EFSM被动测试变量管理器的实现 变量管理器框架 EFSM被动测试变量管理器的实现 可能值区间 Value类的数据结构 private ELEMENT TYPEupper lower 取值区间的上确界和下确界boolerror 是否在运算中发生错误 用于错误传播的控制 public boolchanged 是否在运算中改变了区间 用于从条件获取信息的传播 基于Value定义的运算规则 EFSM被动测试变量管理器的实现 变迁条件的描述 析取范式从条件中获取变量值 ImplicationActions EFSM被动测试变量管理器的实现 Assertion的描述 合取范式和取范式有利于做Assertion去冗余处理 判断和取范式中每一个合取项 如果能被变量值确定的描述 则该合取项为冗余信息 EFSM被动测试变量管理器的实现 条件的描述 EFSM被动测试变量管理器的实现 表达式的描述 EFSM被动测试变量管理器的实现 Action的分析过程 易于移植的Watcher结构 历史 BGPWatcher BGPWatcherforPassiveTesting OSPFWatcherforPassiveTesting ProtocolWatcher结构 OSPFWatcher ProtocolWatcher ProtocolWatcher 对于一个新的协议 需要重新设计的模块有 l根据协议设计数据包的数据结构 文件结构和缓冲结构l根据新的文件结构 缓冲结构重新设计文件和缓冲的初始化模块和结束模块l重新设计事件处理器模块l重新设计各层的过滤器 其实大多数过滤器是不需要的 直接返回允许通过即可 l可选 重新设计可视化模块 ProtocolWatcher 接口模块设计规范 初始化模块Intevent handler init void 包处理模块Intevent handler process char buf intlen 完成模块Intevent handler done void MAC层过滤模块intProtocolFilter char buf intlen 未来工作展望 在理论上对现有的EFSM变量管理算法进行复杂性分析 提高算法效率 在EFSM