Configuration Format - prasadtalasila/BITS-Darshini GitHub Wiki

(To add details of: [OpenState])

This wiki page details the thoughts behind the selection of a configuration language and data type format for packet parser.

The primary function of a packet analyzer software is to parse all the headers of the incoming packets. In order to perform this function efficiently, the packet parser must be aware of the specification of all of the header fields of all the protocols of interest. Past work on the specification of packet headers for the purposes of packet parsing has useful proposals in this direction.

One of the earliest works in the area of generic specification of packet headers was by Vern Paxson in his Bro scripting language [Bro]. Bro scripting language provides default data types (ex: int, double, bool) and network-specific data types (ex: port, addr for IP address, hostname for DNS names); the Bro language also allows records (composite structures) on the supported data types as well (ex: connection_id for tracking a flow).

Next came a very influential packet format specification named Packet Types from McCann and Chandra in 2000 [PacketTypes]. The Packet Types uses byte and bytestring as the primitive types and build nybble, short, long, ipaddress, and ipoptions as derivate packet types. The sample specification of IP header from the paper is as shown below.

Primitive types byte := bit[8];
bytestring := byte[]; ([] is a repetition operator, [n] specifies the number of repetitions)
nybble := bit [4]
short := bit [16]
long := bit [32]
ipaddress := byte [4]
ipoptions := bytestring

IP_PDU := {

nybble version;
nybble ihl;
byte tos;
short totallength;
short identification;
bit morefrags;
bit dontfrag;
bit unused;
bit frag_off[13];
byte ttl;
byte protocol;
short cksum;
ipaddress src;
ipaddress dest;
ipoptions options;
bytestring payload;

} where {

version#value = 0x04;
options#numbytes = ihl#value * 4 - 20;
payload#numbytes = totallength#value - ihl#value * 4;

}

There is a :> operator for type refinement (in simple terms, layering in networking). An example is shown below.

IPinEthernet :> Ethernet_PDU where {

type#value = 0x0800
overlay payload with IP_PDU

}

The user-defined constraints can be specified as,

My_IPinEthernet :> IPinEthernet where {

payload.srcaddr#value = 192.168.0.1

}

Another operator proposed is |= for alternation (in simple terms, options in networking). An example is shown below.

ipoptions := {

NonEndOption neo[];
EndOption eo[];
bytestring padding;

} where {

eo#numelems <= 1;

}

With the NoEndOption to be specified as following.

NonEndOption |= {

NoOperation nop;
Security sec;
LSRR lsrr;
SSRR ssrr;
RR rr;
StreamID sid;
Timestamp tstamp;

}

With the alternation operator, we say that any of the options specified can appear in the packet. The proposals of this paper are the intellectual predecessor to most of the proposals in the [P4] paper. For more details, see sections 2 and 3 of [PacketTypes].

{DataScript 2002, PPL 2004, PADS 2005, PacketC 2009 -- similar to PackeetTypes, Attig2011 - keybuilder, P4 2014}

The header fields of the protocols of interest can be specified in a C-language structure like format.

The way the following concepts of P4 language get mapped to the packet parsing software also need to be discussed.

  1. Header format specification (utilized on the server-side)
  2. Parse graph (generated on client side, DPD)
  3. Match table (null at present, NERL 2002, Bro 1999)
  4. Action methods (store to DB at present, Bro 1999)
  5. Control (none at present)

The missing part is the semantic constraints on the header formats. P4 language need to be extended in this direction. There are already good ideas in the selected packet parsing language papers on this topic.

References

  1. [NetConf] Munz, G., Antony, A., Dressler, F. and Carle, G., 2006, April. Using netconf for configuring monitoring probes. In Network Operations and Management Symposium, 2006. NOMS 2006. 10th IEEE/IFIP (pp. 1-4). IEEE.
  2. [P4] Bossart, P. et al., P4: Programming Protocol-Independent Packet Processors, ACM SIGCOMM Computer Communications Review, Volume 44, Number 3, July 2014.
  3. [PacketC] Duncan, R. and Jungck, P., 2009, June. packetC language for high performance packet processing. In High Performance Computing and Communications, 2009. HPCC'09. 11th IEEE International Conference on (pp. 450-457). IEEE.
  4. [PacketTypes] McCann, P.J. and Chandra, S., 2000. Packet types: abstract specification of network protocol messages. ACM SIGCOMM Computer Communication Review, 30(4), pp.321-333.
  5. [Gibb2013] Gibb, G., Varghese, G., Horowitz, M. and McKeown, N., 2013, October. Design principles for packet parsers. In Architectures for Networking and Communications Systems (ANCS), 2013 ACM/IEEE Symposium on (pp. 13-24). IEEE.
  6. [McCanne1993] McCanne, S. and Jacobson, V., 1993, January. The BSD packet filter: A new architecture for user-level packet capture. In Proceedings of the USENIX Winter 1993 Conference Proceedings on USENIX Winter 1993 Conference Proceedings (pp. 2-2). USENIX Association.
  7. [Attig2011] Attig, M. and Brebner, G., 2011, October. 400 gb/s programmable packet parsing on a single fpga. In Proceedings of the 2011 ACM/IEEE Seventh Symposium on Architectures for Networking and Communications Systems (pp. 12-23). IEEE Computer Society.
  8. [AutoParserP4] Benácek, P., Puš, V. and Kubátová, H., Automatic Generation of 100 Gbps Packet Parsers from P4.
  9. [OpenState] Bianchi, G., Bonola, M., Capone, A. and Cascone, C., 2014. OpenState: programming platform-independent stateful openflow applications inside the switch. ACM SIGCOMM Computer Communication Review, 44(2), pp.44-51.
  10. [PADS] Fisher, K. and Gruber, R., 2005. PADS: a domain-specific language for processing ad hoc data. ACM Sigplan Notices, 40(6), pp.295-304.
  11. [NERL] Bhargavan, K. and Gunter, C.A., 2002. Requirements for a practical network event recognition language. Electronic Notes in Theoretical Computer Science, 70(4), pp.1-20.
  12. [DataScript] Back, G., 2002, October. DataScript-A specification and scripting language for binary data. In Generative Programming and Component Engineering (pp. 66-77). Springer Berlin Heidelberg.
  13. [Bro] Paxson, V., 1999. Bro: a system for detecting network intruders in real-time. Computer networks, 31(23), pp.2435-2463.
  14. [PPL] Krupski, E.G., 2004. {PPL: a Packet Processing Language}.