基于状态机对故障模式进行了统一的描述,使得故障描述更准确、无二义性。为了避免路径组合爆炸,提出基于控制流的状态集迭代分析算法进行故障检测,可以使算法的计算复杂性由O(P)(P是路径数目)减少为O(N+E)N)(N是控制流图节点数,E是控制流图边数)。由于状态机的独立性,对控制流图进行一遍迭代可以同时计算多个故障模式,大大提高测试效率。同时,该方法还采用了带条件的状态计算可以较好地减少误报的情况。
Abstract
This paper uses state machines to give a formal and unified description of fault patterns. Then, a unified testing method based on iteration of state set is pro posed to avoid the pathexplosion problem. The algorithm's computing complexity is O((N+E)N)(N is the number of nodes in control flow graph,E is nu mber of edges in control flow graph). Because of the independency of the state machine, one traversal of control flow can test many fault patterns, therefore, testing efficiency can be can improved. Moreover, the paper uses conditional sta te computing to reduce the problem of false positives.
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
参考文献
[1]BALL T, BOUNIMOVA E, COOK B. Thorough static analysis of devi ce drivers[C]∥EuroSys, 2006: 73-85.
[2]YANG J, SAR C, ENGLER D. Explode: a lightweight,general system for fi nding serious storage system errors[C]∥OSDI, 2006:131-146.
[3]ENGLER D, CHELF B, CHOU A, et al. Checking system rules using systemspe cific, programmerwritten compiler extensions[C]∥The Fourth Symposium on Op erating Systems Design and Implementation, 2000: 1-16.
[4]ASHCRAFT K, ENGLER D. Using programmerwritten compiler extensions to ca tch security holes[C]∥IEEE Symposium on Security and Privacy, 2002: 143-159.
[5]HOVEMEYER D, PUGH W. Finding bugs is easy[J]. ACM SIGPLAN Notices, 2004 , 39(12): 92-106.
[6]HALLEM S, CHELF B, XIE Y, et al. A system and language for building syste mspecific, static analyses[C]∥PLDI, 2002: 69-82.
[7]DAS M, LERNER S, SEIGLE M. Pathsensitive program verification in polyno mial time[C]∥PLDI, 2002: 57-68.
[8]AHO A V, SETHI R, ULLMAN J D. Compilers: principles, techniques, and tool s[M]. Beijing: Posts & Telecom Press, Pearson Education, 2002: 608-633.
{{custom_fnGroup.title_cn}}
脚注
{{custom_fn.content}}