MID-008: Decidable Protocols and Parsers

Mitigation Tier: Intermediate

Description

One way to understand a protocol’s complexity is through a computational theoretic perspective (e.g., LangSec). For example, the Chomsky hierarchical rank of the grammar used to create a protocol directly dictates the minimum computational model necessary to recognize and parse the protocol. Therefore, 1) structured data and protocols should be designed using the lowest level grammar possible so that 2) parsers can be made using minimally and appropriately matched computational models (e.g., a deterministic push-down automata being used to parse context free input languages instead of a Turing machine).

1. Regarding implementing your own protocol

The design of any new protocol should include an understanding of the grammar used to create that protocol and the computational model necessary to parse that protocol to ensure that the language can be correctly represented by a decidable computational model, particularly with regard to the equivalence problem. This would mean building a protocol out of a regular or deterministic context-free grammar.

Unless a protocol or input language can be built from a regular or deterministic context-free grammar, any corresponding parsers cannot be built to be recognizers and parsers of that protocol without being made undecidable with regard to the equivalence problem and maintain full protocol functionality. This is important because if a parser built to run over an undecidable grammar with regard to the equivalence problem, it will be impossible to guarantee that the parser does not enter an unwanted or vulnerable state. This makes the parser have a higher chance of exhibiting exploitable behaviors.

2. Regarding implementing your own parser

The design of any new protocol parser should be made such that the computational model of that parser conforms to the minimally sufficient computational model necessary to parse that protocol. If a protocol parser is made to be more complex than the grammar used to make the protocol would otherwise require, threat actors may be able to discover unwanted or vulnerable states that could lead to exploitation. Minimally necessary computational models, ideally ones that are decidable with regard to the equivalence problem, allow for machine states to be checked and give threat actors less opportunities to exploit parser behavior.

IEC 62443 4-2 Mappings

• none

References

[1] L. Sassaman, M. L. Patterson, S. Bratus, A. Shubina, “The Halting Problems of Network Stack Insecurity,” USENIX ;login:, vol. 36, no. 6, pp. 22-32, Dec. 2011. [Online]. Available: https://www.usenix.org/legacy/publications/login/2011-12/openpdfs/Sassaman.pdf

[2] “LangSec: Recognition, Validation, and Compositional Correctness for Real World Security.” Accessed: Aug. 27, 2024. [Online]. Available: http://langsec.org/bof-handout.pdf

[3] Sergey Bratus, Adam J. Crain, Sven M. Hallberg, Daniel P. Hirsch, Meredith L. Patterson, Maxwell Koo, and Sean W. Smith. 2016. Implementing a vertically hardened DNP3 control stack for power applications. In Proceedings of the 2nd Annual Industrial Control System Security Workshop (ICSS ‘16). Association for Computing Machinery, New York, NY, USA, 45–53.

MID-008