Path-based protocol verification approach

檔案

日期

2000-03-01

類型

期刊名稱

INFORMATION AND SOFTWARE TECHNOLOGY

卷期與頁次

第 42 卷第 4 期,頁 229–244

ISSN

0950-5849

語言

英文

摘要

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.

所屬典藏

期刊論文
顯示完整詮釋資料 統計資料

引用此條目

Liu, W., & Chung, C. (2000). Path-based protocol verification approach. INFORMATION AND SOFTWARE TECHNOLOGY, 42(4), 229–244. https://doi.org/10.1016/S0950-5849(99)00061-0

BibTeX RIS

引用文字依 APA 第 7 版格式自動產生,使用前請再核對。

分享

永久網址:https://ir.lib.nycu.edu.tw/handle/11536/30669