Hardware Sequence Combinators

Abstract

Recent advances in formal methods for constructing parsers have employed the notion of combinators: primitive elemental parsers with well-defined methods for combining them in sequences or through choice. This paper explores the subtleties associated with leveraging sequence combinators to produce compact, custom hardware traffic validators. This involves a fully automated process that takes as input a formal grammar specifying message formats and produces a parsing circuit capable of validating traffic headers and payload content. The resulting circuit is deployed through network guard appliances that employ Field Programmable Gate Array (FPGA) devices, or alternatively, within the on-chip FPGA associated with System-on-Chip (SoC) devices, such as the Xilinx UltraScale MPSoC. Each guard appliance acts as a hidden “bump-in-the-wire” that either forwards or drops individual packets based on the message parsing outcome, thereby hardening network segments against zero-day attacks and persistent implants. Guards may operate on a wide variety traffic protocols and formats including TCP/IP, CAN/J1939, or MIL-STD-1553. The central step in parser construction is to build a collection of standard shift/reduce parsing tables that can be employed by a push-down automata to check each byte in a message. Typically, these tables are sparse, resulting in excessive use of FPGA circuit resources to represent them. By leveraging sequence combinators, along with other optimizations, we have been able to produce highly compact representations that can reduce table size by up to 95% for non-trivial grammars. Depending on the grammar, this translates directly into FPGA resource reductions. The reductions now make it viable to implement complex parsers on small, inexpensive FPGA’s, or alternatively combine parsers with encryption and encapsulation to enhance guard capabilities.