標題: Path-based protocol verification approach
作者: Liu, WC
Chung, CG
資訊工程學系
Department of Computer Science
關鍵字: protocol verification;concurrent path;path-based verification
公開日期: 1-Mar-2000
摘要: Protocol verification is one of the most challenging tasks in the design of protocols. Among the various proposed approaches, the one based on reachability analysis (or known as state enumeration approach) is of the most: simple, automatic and effective. However, the state explosion problem is a principle obstacle toward successful and complete verifications of complex protocols. To overcome this problem, we proposed a new approach, the "path-based approach." The idea is to divide a protocol into a collection of individual execution record, denoted as: concurrent paths, a partial order representation recording the execution paths of individual entities. Then, the verification of the protocol is, thus, replaced by that of individual concurrent paths. Since concurrent paths can be automatically generated through Cartesian product:of the execution paths of all modules, and verified independently, the memory requirement is limited to the complexity of individual concurrent path rather than the whole protocol. Thus, the state explosion problem is alleviated from such "divide and conquer" approach. Furthermore, we propose an algorithm, making the trade-off on memory requirement to generate the concurrent paths more efficiently; and utilize the technique of symmetric verification, parallel computing to improve the efficiency of verification. Eventually, our experience of verifying real protocols shows that our approach uses much less memory:and time than reachability analysis. (C) 2000 Elsevier Science B.V. All rights reserved.
URI: http://dx.doi.org/10.1016/S0950-5849(99)00061-0
http://hdl.handle.net/11536/30669
ISSN: 0950-5849
DOI: 10.1016/S0950-5849(99)00061-0
期刊: INFORMATION AND SOFTWARE TECHNOLOGY
Volume: 42
Issue: 4
起始頁: 229
結束頁: 244
Appears in Collections:Articles


Files in This Item:

  1. 000085869800001.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.