Timed Interpreted Systems as a New Agent-Based Formalism for Verification of Timed Security Protocols

This article introduces a new method for modelling and verifying the execution of timed security protocols (TSP) and their time-dependent security properties. The method, which is both novel and reliable, uses an extension of interpreted systems, accessible semantics in multi-agent systems, and timed interpreted systems (TIS) with dense time semantics to model TSP executions. We enhance the models of TSPs by incorporating delays and varying lifetimes to capture real-life aspects of protocol executions. To illustrate the method, we model a timed version of the Needham-Schroeder Public Key Authentication Protocol. We have also developed a new SMT-based bounded model checking reachability algorithm for the proposed structures and implemented it with the tool. The method comprises a new procedure for modelling TSP executions, a translation of TSP into TIS, and a translation of TIS's reachability problem into the SMT problem. The paper also includes thorough experimental results for nine protocols modelled by TIS and discusses the findings in detail.