Protocol Interoperability testing is an important means to ensure the interconnection and interoperation between protocol products. In this paper, we proposed a formal approach to protocol interoperability testing based on the operational semantics of Concurrent TTCN. We define Concurrent TTCN’s operational semantics by using Labeled transition System, and describe the interoperability test execution and test verdict based on Concurrent TTCN. This approach is very helpful for the formation of formal interoperability testing theory and construction of general interoperability testing system. Protocol interoperability testing is an important means to ensure the interconnection and interoperation between protocol products. In this paper, we proposed a formal approach to protocol interoperability testing based on the operational semantics of Concurrent TTCN. We define Concurrent TTCN’s operational semantics by using Labeled Transition System , and describe the interoperability test execution and test verdict based on Concurrent TTCN. This approach is very helpful for the formation of formal interoperability testing theory and construction of general interoperability testing system.