关键词:
层次着色Petri网
多线程JAVA程序
自动建模
模型检测
摘要:
随着软件系统的广泛应用,多线程软件已经成为一类主流的软件系统,算法错误检测也越来越重要。由于并发行为的不确定性,多线程JAVA程序的算法错误检测非常困难,正确性难以保证。传统的基于模型的检测方法存在两方面的弊端,一是手工建模,模型的正确性不易保证,二是建模的工作量很大,效率偏低。因此,本文提出一种多线程JAVA程序的层次着色Petri网(Hierarchical Colored Petri Net,HCPN)模型的自动生成方法。一方面,生成HCPN模型的过程实现了自动化,提升建模效率;另一方面,本文针对程序实现建模,保证了程序和模型的一致性。本文完成了如下工作:(1)多线程程序读取及存储方法:对多线程JAVA程序进行读入、分析及存储处理。其中类声明、函数声明、变量声明语句采用链表存储,每个函数内的程序处理语句采用一棵语句二叉树存储,通过树中当前语句结点的左右子结点区分后续语句的嵌套关系和顺序关系。(2)HCPN模型生成方法:基于声明链表和语句二叉树中的程序信息生成HCPN模型。在模型中采用token流转描述程序中的变量,用颜色集实现变量类型描述,用变量组支持token流转,其中对象依据类的数据成员采用元组处理。用模型子页和替代变迁描述函数定义及函数调用,用模型中的并发结构描述程序中的多线程并发,采用融合集实现全局变量和静态变量在线程间的交互。不同类型的程序处理语句通过相应的标准模型片段完成描述,程序语句的顺序和嵌套关系采用模型片段的连接和嵌套实现。(3)模型文件生成方法:将生成的HCPN模型以CPN Tools标准格式文件输出,该文件可以在CPN Tools中打开并进行ASK-CTL模型检测。最后,通过实例应用及执行效果分析验证了本方法的正确性,说明本文提出的方法能够自动生成与多线程JAVA程序一致的HCPN模型,为后续的粗粒度自动建模方法及模型检测方法研究提供基础。