Assuring string pattern matching in outsourced middleboxes

Xingliang Yuan, Huayi Duan, Cong Wang

Research output: Contribution to journalArticleResearchpeer-review

14 Citations (Scopus)


Modern enterprise networks heavily rely on the ubiquitous network middleboxes for advanced traffic processing functions. Recent advances in software packet processing and virtualization technologies are further pushing forward the paradigm of migrating middleboxes to third-party providers, e.g., clouds and ISPs, as virtualized services, with well-understood benefits on reduced maintenance cost and increased service scalability. Despite promising, outsourcing middleboxes raises new security challenges. Among others, this new service eliminates the enterprise's direct control on outsourced network functions. Mechanisms assuring that those middleboxes consistently perform network functions as intended currently do not exist. In this paper, we propose the first practical system that enables runtime execution assurances of outsourced middleboxes with high confidence, helping enterprises to extend their visibility into untrusted service providers. As an initial effort, we target on pattern matching-based network functions, which cover a broad class of middlebox applications, such as instruction detection, Web firewall, and traffic classification. Our design follows the roadmap of probabilistic checking mechanisms that provide a tunable level of assurance, as in cloud and distributed computing literature. We show how to synthesize this design intuition in the context of outsourced middleboxes and the dynamic network effect. Specifically, we present diligent technical instantiations in the cases of the single middlebox and the composition (i.e., service chaining). We deploy our designs into off-the-shelf middlebox outsourcing architectures with full-fledged implementation on the click modular router. Evaluations demonstrate that high assurance levels are achieved by pre-processing only a few packets with marginal overhead.

Original languageEnglish
Pages (from-to)1362-1375
Number of pages14
JournalIEEE/ACM Transactions on Networking
Issue number3
Publication statusPublished - Jun 2018


  • computer network reliability
  • cryptographic protocols
  • middleboxes
  • Network function virtualization
  • network security

Cite this