Computer Science ›› 2016, Vol. 43 ›› Issue (2): 113-117, 134.doi: 10.11896/j.issn.1002-137X.2016.02.026

Previous Articles     Next Articles

xMAS-based Formal Verification of SpaceWire Credit Logic

LI Yan-chun, LI Xiao-juan, GUAN Yong, WANG Rui, ZHANG Jie and WEI Hong-xing   

  • Online:2018-12-01 Published:2018-12-01

Abstract: SpaceWire protocol is a high-speed communication bus protocol applied to aerospace,so it is very important for communication system to ensure the reliability of the design.Due to the presence of a large number of queues,distributed control and concurrency,the traditional verification methods have incomplete defects and state explosion when model checking occurs.This paper presented a formal verification method of credit logic in SpaceWire communication system with xMAS model.xMAS model retains the structural information in lower level and can verify high-level attri-butes.The paper built an abstract xMAS model for credit logic and listed three key properties including sending,receiving and data consistency.Correctness of the properties was verified automatically by the ACL2 theorem proving tool.It can provide effective reference for system design under the guidance of verification.

Key words: xMAS model,Credit logic,SpaceWire,Formal verification,ACL2

[1] ECSS.Space Engineering:SpaceWire-Links,nodes,routers,and networks(ECSS-E-50-12A)[S].The Netherlands:ESA Publications Division ESTEC,2003
[2] Chatterjee S,Kishinevsky M.Automatic Generation of Inductive Invariants from High-Level Microarchitectu-ral Models of Communication Fabrics[J].Formal Methods in System Design,2012,40(2):147-169
[3] Verbeek F,Schmaltz J.Hunting deadlocks efficiently in microarchitectural models of communication fabrics[C]∥Formal Me-thods in Computer-Aided Design(FMCAD).2011:223-231
[4] Chatterjee S,Kishinevsky M O.Quick formal modeling of communication fabrics to enable verification[C]∥High Level Design Validation and TestWorkshop (HLDVT).IEEE,2010:42-49
[5] Gotmanov A,Chatterjee S,Kishinevsky M.Verifying deadlock-freedom of communication fabrics[C]∥Verification,Model Checking,and Interpretation (VMCAI).2011:214-231
[6] Ray S,Brayton R K.Scalable Progress Verification in Credit-Based Flow-Control Systems[C]∥Design,Automation & Test in Europe Conference & Exhibition(DATE).2012:905-910
[7] Borrione D,Helmy A,Pierre L,et al.A generic model for formally verifying NoC communication architectures:a case study[C]∥Networks-on-Chip (NOCS).2007:127-136
[8] Verbeek F.Formal Verification of on-Chip Communication Fabrics[M].Radboud University Nijmegen,2013
[9] van Gastel B,Schmaltz J.A formalisation of XMAS[C]∥Electronic Proceeding in Theoretical Computer Science(EPTCS).2013:111-126
[10] Kaufmann M,Moore J S,Manolios P.Computer-Aided Reaso-ning:An Approach[M].Norwell,MA:Kluwer Academic Publishers,2000
[11] Kaufmann M,Moore J S,Manolios P.Computer-Aided Reaso-ning:ACL2 Case Studies[M].Norwell,MA:Kluwer Academic Publishers,2000
[12] Joosten S J C,Verbeek F,Schmaltz J.WickedXmas:Designing and Verifying on-chip Communication Fabrics[C]∥Design and Implementation of Formal Tools and Systems(DIFTS).2014:1-8
[13] Kishinevsky M,Gotmanov A,Viktorov Y.Challenges in Verifying Communication Fabrics[C]∥Interactive theorem proving (ITP).2011:18-21
[14] Zhang Yu-peng,Shi Zhi-ping,Guan Yong,et al.Formal Verification of SpaceWire Decoding Circuit in HOL4[J].Journal of Chinese Systems,2013,8:1959-1963(in Chinese) 张玉鹏,施智平,关永,等.SpaceWire译码电路在HOL4中的形式化[J].小型微型计算机系统,2013,8:1959-1963
[15] Dong Ling-ling,Guan Yong,Li Xiao-juan,et al.Verification for SpaceWire error detection mechanism by LTL model checking [J].Computer Engineering and Applications,2012,8(22):88-94(in Chinese) 董玲玲,关永,李晓娟,等.用LTL模型检验的方法验证SpaceWire检错机制[J].计算机工程与应用,2012,8(22):88-94

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75, 88 .
[2] XIA Qing-xun and ZHUANG Yi. Remote Attestation Mechanism Based on Locality Principle[J]. Computer Science, 2018, 45(4): 148 -151, 162 .
[3] LI Bai-shen, LI Ling-zhi, SUN Yong and ZHU Yan-qin. Intranet Defense Algorithm Based on Pseudo Boosting Decision Tree[J]. Computer Science, 2018, 45(4): 157 -162 .
[4] WANG Huan, ZHANG Yun-feng and ZHANG Yan. Rapid Decision Method for Repairing Sequence Based on CFDs[J]. Computer Science, 2018, 45(3): 311 -316 .
[5] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[6] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[7] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[8] LIU Qin. Study on Data Quality Based on Constraint in Computer Forensics[J]. Computer Science, 2018, 45(4): 169 -172 .
[9] ZHONG Fei and YANG Bin. License Plate Detection Based on Principal Component Analysis Network[J]. Computer Science, 2018, 45(3): 268 -273 .
[10] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99, 116 .