[langsec-discuss] Parallel Systems/Automata

Sergey Bratus sergey at cs.dartmouth.edu
Tue Jun 18 21:07:58 UTC 2013

    Supporting FX's analysis, I think there is additional confusion w.r.t. 
what is being parallelized.

    One can try to parse different parts of a single, stand-alone message 
in parallel. For large messages, this can be theoretically interesting 
(although dangerous), but I don't think applying this to packets of 
typical sizes would deliver any performance gains.

    Then one can try to parse a number of messages in parallel (say, 
packets from some time window interval, in no particular order). For 
stateless protocols, such parallelization is trivial, since there is no 
common state for the individual message parsers to maintain and update. 
Presuming the non-trivial case when message are somehow related by order, 
and their relation is expressed through some shared state, the individual 
message parsers would need to have a protocol to speculatively maintain 
that state, including discarding it if recognition fails.

    Such state-keeping protocol would make an interesting -- but again, 
dangerous and hard to correctly implement -- design exercise. My hunch is 
that it would probably be too complex to implement in actual network 

    The complexity of such parallelization would also suggest that 
protocols in which parsing of subsequent messages is non-trivially 
governed by the context created by previous messages will be a
challenge to securely parse.



On Tue, 18 Jun 2013, Felix 'FX' Lindner wrote:

> Hi,
> On Tue, 18 Jun 2013 10:31:25 +0200 Fabian Fäßler <fabi at fabif.de> wrote:
>> But then he told me that in the networking environment you have to
>> think in parallel and the LANGSEC idea is probably very different in
>> such an environment. He was talking about the Switches and Routers,
>> which have dozens of cables to process packets in parallel
>> (forwarding, rerouting or setting up internal databases). So
>> basically you have independent automata interacting with each other
>> through messages.
> having looked at one or two routers in my life, I strongly disagree
> with your supervisor's view.
> People writing code in the OSI Layer 2 and 3 worlds, specifically
> router vendors, focus solely on "line speed", meaning how much packet
> data can they forward per unit of time (while I think the term is more
> telling about certain practices in marketing departments of said
> vendors).
> They use the performance argument to justify their shotgun parsers.
> While a perfect 802.2 Ethernet switch is a single pellet shotgun parser
> (reads 6 bytes at fixed offset), it doesn't mean that all other code is
> fine doing the same, just because it's in network equipment. Look at
> the nightmare that is IPv6 RA guard and extention headers. This is the
> result of people ignoring the message of full recognition before
> processing. Sure it's slower, but there is no big router I know where
> you even have the choice. They all try to put more pellets in their
> shotgun parser shells and hope to hit something. Since this is bound to
> fail, there is a debate about disallowing extention headers from IPv6
> ICMP, meaning the spec is modified because the shotgun is not working.
> What your supervisor probably thinks of is the current reality: You
> watch as many shotguns as you have interfaces going off at more or less
> the same time. Now go and try make sense of the packet splater in your
> IO memory. If you do it wrong, doing it in parallel rarely makes it
> better.
> I'm sure that parallel automata are a very interesting topic, but I
> don't think they apply in this case (please correct me if I'm wrong).
> Once a full recognition is completed, you will have a nice and
> ordered list of packets/frames received that you can perform your
> processing on - and only valid packets they are.
> cheers
> FX
> -- 
> Recurity Labs GmbH           | Felix 'FX' Lindner
> http://www.recurity-labs.com | fx at recurity-labs.com
> Wrangelstrasse 4             | Fon: +49 30 69539993-0
> 10997 Berlin                 | PGP: A740 DE51 9891 19DF 0D05
> Germany                      |      13B3 1759 C388 C92D 6BBB
> HRB 105213 B, Amtsgericht Charlottenburg, GF Felix Lindner
> _______________________________________________
> langsec-discuss mailing list
> langsec-discuss at mail.langsec.org
> https://mail.langsec.org/cgi-bin/mailman/listinfo/langsec-discuss

More information about the langsec-discuss mailing list