好文档就是一把金锄头!
欢迎来到金锄头文库![会员中心]
电子文档交易市场
安卓APP | ios版本
电子文档交易市场
安卓APP | ios版本

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

25页
  • 卖家[上传人]:枫**
  • 文档编号:588959046
  • 上传时间:2024-09-09
  • 文档格式:PPT
  • 文档大小:360.50KB
  • / 25 举报 版权申诉 马上下载
  • 文本预览
  • 下载提示
  • 常见问题
    • FSM/EFSM的被动测试算法及其在BGP/OSPF协议测试的实现答辩人:魏小亮指导教师:吴建平 教授2001年6月1 主要内容l选题背景l完成的主要工作l被动测试系统结构lEFSM被动测试变量管理的算法研究lEFSM被动测试变量管理器的实现l易于移植的Watcher结构l未来工作展望2 选题背景l1972年:被动测试被提出但没有有效算法l1997年:D. Lee提出FSM/NFSM模型的被动测试算法l1998年:R. Miller提出CFSM模型的被动测试算法lEFSM模型的被动测试算法?l用于实际协议测试的算法?3 完成的主要工作l算法:EFSM被动测试算法中的变量管理l实现:FSM模型描述BGP协议的被动测试器NFSM/EFSM模型描述OSPF的被动测试器l实验:模拟协议实现(学习NS2/Socrates)数据收集(BW的修改,OW)数据的处理(BGP/OSPF的包解析器等)4 FSM被动测试系统结构5 EFSM被动测试系统结构6 EFSM被动测试的变量管理现有的方案:lNFSM不考虑变量的问题测试能力?l区域状态机的思路EFSM—(变量区间×状态)FSM如何记录可能的可能的可能的可能的状态?l放弃不确定的变量值[Tabour99 ]不分裂状态,放弃记录有多个可能取值的变量7 EFSM被动测试的变量管理提出的方案:l用区间记录可能的取值“区域自动机”——“放弃不确定值”的折衷方案l利用条件获取信息发生了变迁条件为(x==c)的变迁x=cl有限度地分裂节点(陈东洛) situation =状态+变量值;可能的situation过多时,把状态相同的situation合并。

      l记录历史信息(陈东洛)不确定变迁条件+不确定动作=assertion(断言)    situation=状态+变量值+assertion (断言)8 EFSM被动测试的变量管理四个方案的综合:l兼容性报错条件——可以漏过一些错误,不能误判每个算法都是遵守被动测试报错条件的,算法的组合仍然满足报错条件 l冗余性可能值区间 vs 记录历史信息历史信息记录的是可能值区间不能记录确定的信息9 EFSM被动测试的综合算法状态控制器算法:数据结构:一个situation队列A,一个situation包括了一组变量值和被测实现当前处在的协议自动机状态1、  等待一个事件;读入一个事件2、  建立一个空的situation队列B(新生成的situation列表)3、  对队列A里面每一个situation S做:对从S发出的每一条满足事件的变迁(输入输出与事件一致)做:A、 复制一个新的situation S’,S’=SB、 以S’为situation,调用变量管理器的transition函数,判断变迁条件是否可满足C、 如果变迁条件满足,则把S’加入到队列B中,否则删除S’5、  清空队列A,把队列B的situation都加入到队列A里面,删除队列B,转110 EFSM被动测试的综合算法变量管理器算法:11 EFSM被动测试变量管理器的实现l变量管理器框架:12 EFSM被动测试变量管理器的实现可能值区间——Value类的数据结构:private:ELEMENT_TYPE upper, lower;//取值区间的上确界和下确界bool error; //是否在运算中发生错误(用于错误传播的控制)public:bool changed; //是否在运算中改变了区间(用于从条件获取信息的传播) 基于Value定义的运算规则13 EFSM被动测试变量管理器的实现变迁条件的描述:析取范式从条件中获取变量值:Implication Actions14 EFSM被动测试变量管理器的实现Assertion的描述:合取范式和取范式有利于做Assertion去冗余处理:判断和取范式中每一个合取项,如果能被变量值确定的描述,则该合取项为冗余信息。

      15 EFSM被动测试变量管理器的实现l条件的描述:16 EFSM被动测试变量管理器的实现l表达式的描述:17 EFSM被动测试变量管理器的实现lAction的分析过程:18 易于移植的Watcher结构历史:BGP WatcherBGP Watcher for Passive TestingOSPF Watcher for Passive TestingProtocol Watcher结构19 OSPF Watcher20 Protocol Watcher21 Protocol Watcher对于一个新的协议,需要重新设计的模块有:ll根据协议设计数据包的数据结构、文件结构和缓冲结构ll根据新的文件结构、缓冲结构重新设计文件和缓冲的初始化模块和结束模块ll重新设计事件处理器模块ll重新设计各层的过滤器(其实大多数过滤器是不需要的,直接返回允许通过即可)ll可选:重新设计可视化模块 22 Protocol Watcher接口模块设计规范:初始化模块初始化模块 lInt event_handler_init(void) 包处理模块包处理模块 Int event_handler_process(char* buf, int len)完成模块完成模块 Int event_handler_done(void) MAC层过滤模块层过滤模块int ProtocolFilter(char *buf,int len) 23 未来工作展望l在理论上对现有的EFSM变量管理算法进行复杂性分析,提高算法效率。

       l在EFSM模型方面,考虑如何做situation合并能最大程度的保存有用信息l引入时间因素,考虑时间状态机的被动测试算法l考虑多台自动机通信的情况,考虑实用的CFSM被动测试算法(要考虑单个自动机是EFSM模型的情况)24 谢谢!Q&A?25 。

      点击阅读更多内容
      关于金锄头网 - 版权申诉 - 免责声明 - 诚邀英才 - 联系我们
      手机版 | 川公网安备 51140202000112号 | 经营许可证(蜀ICP备13022795号)
      ©2008-2016 by Sichuan Goldhoe Inc. All Rights Reserved.