基于执行序列的嵌入式软件时序异常检测  

Temporal Defect Detection of Embedded Software Using Timed Execution Trace

作　　者：王博[1,2] 白晓颖[1,2] 陈文光[1,2] SONG Xiaoyu WANG Bo;BAI Xiao-Ying;CHEN Wen-Guang;SONG Xiaoyu(Department of Computer Science and Technology,Tsinghua University,Beijing100084;National Laboratory for Information Science and Technology,Tsinghua University,Beijing100084;Department of Electrical and Computer Engineering,Portland State University,Portland,97207,USA)

机构地区：[1]清华大学计算机科学与技术系,北京100084 [2]清华大学信息科学与技术国家实验室,北京100084 [3]波特兰州立大学电气与计算机工程系,美国波特兰97207

出　　处：《计算机学报》2017年第12期2635-2657,共23页Chinese Journal of Computers

基　　金：国家自然科学基金(91218302;61472197);北京市自然科学基金(4132062)资助~~

摘　　要：时序特性是嵌入式软件的重要特性,实时嵌入式软件运行的正确性不仅依赖于任务执行结果,更依赖于任务执行时间.执行任务往往具有多个时间约束,且相互之间可能存在制约关系,对时间约束进行验证和确认是嵌入式软件测试的一个重要问题.文中提出一种基于执行片段的嵌入式软件时序特性检测方法(Trace-Based Temporal Defect Detection,TBTDD).一方面,基于扩展语义接口自动机(Extended Semantic Interface Automata,ESIA)模型,刻画嵌入式软件时序特性需求,分析不同时间约束间存在的相关关系类型,并提出基于相关矩阵的相关时间约束识别算法;另一方面,在目标软件运行环境中提取包含时间信息的执行片段,通过执行片段与时间约束模型的匹配,依据预先制定的时序特性检测准则,检验执行序列是否满足模型中各项独立和相关时间约束的要求,进而发现被测软件中存在的时序缺陷.实验以卫星定位系统软件为例进行建模与缺陷检测,并在执行片段集和缺陷检测能力等方面进行了对比分析.实验表明,该方法可有效检测软件运行过程中存在的各类异常时序,提高了软件时序测试的有效性和充分性.Temporal requirements are critical to embedded software.The correctness of system operation depends on its satisfications to the timing constraints.In an embedded system,there usually exist many timing constraints which may also correlate with each other.It is important to ensure that the execution of the system conforms to its temporal requirements.The paper proposes an approach for detecting temporal defects based on execution traces analysis.The characteristics of timing constraints are analyzed,and the ESIA(Extended Semantic Interface Automata)is proposed to characterize temporal requirements of embedded software.Then the correlation patterns of timing constraints are analyzed,and an algorithm using timing matrix is proposed to identify the correlated timing constraints in ESIA model.Traces tagged with time stamps are gathered from the execution environment of the target software.According to the temporal checking rules predefined,the traces are matched to the temporal model to verify its conformance to timing constraints,both individual as well as correlated constraints.In case violations detected,potential defects will be reported for further investigation.Experiments are exercised on a satellite positioning system for modeling and defect detection.The results are compared with other approaches in terms traces analysis and defect detection capabilities.It showed that the proposed approach can effectively detect temporal anomalies in system execution,which enhance the effectiveness and efficiency of temporal testing of embedded software.

关 键 词：接口自动机 时间约束 执行片段 相关性分析 时序缺陷检测 软件测试 嵌入式软件 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]