Understanding the Network Traffic Constraints for Deep Packet Inspection by Passive Measurement (ICISE 2018)

[wkrp]

In two weeks, let's do another live reading group. Like the last one, this one is from the perspective of the "other side." It's about how network conditions affect the performance of a deep packet inspection system.

Sunday, 2023-08-20 13:00–14:00

"Understanding the Network Traffic Constraints for Deep Packet Inspection by Passive Measurement"
刘军 (Liu Jun), 郑超 (Zheng Chao), 郭莉 (Guo Li), 刘学利 (Liu Xueli), 陆秋文 (Lu Qiuwen)
PDF

This one is pretty short, just 6 pages. As usual, we'll meet on Jitsi for one hour to summarize and ask questions about the paper.

I originally aimed to do six of these live reading groups. This will be number five, so I'm planning to organize this one and then one more.

[wkrp]

Understanding the Network Traffic Constraints for Deep Packet Inspection by Passive Measurement
刘军 (Liu Jun), 郑超 (Zheng Chao), 郭莉 (Guo Li), 刘学利 (Liu Xueli), 陆秋文 (Lu Qiuwen)
https://ieeexplore.ieee.org/document/8614475

The paper describes a passive measurement system to quantify various network quality indicators (e.g. round trip time, packet loss rate) that might affect the efficiency of a DPI system. The authors deploy the system in 6 data centers of an ISP and comment on the observed values of the indicators (Section V). The paper does not go into detail on exactly how these indicators affect DPI, except in general terms. Perhaps the most interesting aspect is the demonstration of the ability to correlate asymmetrically routed TCP flows whose upstream and downstream directions go through different data centers, by collecting packet data and processing it centrally.

The 43 network quality indicators appear in Table 1, divided into 4 categories:

• Basic information (18 metrics)

  1. ISP
  2. area addr(?)
  3. data center
  4. inspection point
  5. init_sequence_C2S
  6. client IP
  7. client port
  8. server IP
  9. server port
  10. create time
  11. total number of packets C2S
  12. total number of packets S2C
  13. total number of bytes C2S
  14. total number of bytes S2C
  15. number of payload-carrying packets C2S
  16. number of payload-carrying packets S2C
  17. flow duration
  18. flow close reason
• Link stability (14 metrics)

  1. delay of SYN_SYNACK
  2. delay of SYNACK_ACK
  3. minimum RTT
  4. maximum RTT
  5. average RTT
  6. standard deviation of RTT
  7. number of duplicate packets C2S
  8. number of duplicate packets S2C
  9. fraction of flows that have duplicate packets
  10. fraction of packets that are duplicates
  11. number of out-of-order packets C2S
  12. number of out-of-order packets S2C
  13. fraction of flows that have out-of-order packets
  14. fraction of packets that are out of order
• Connection integrity (5 metrics)

  1. three-way handshake completeness
  2. number of missing packets
  3. number of missing bytes
  4. fraction of flows with missing packets
  5. fraction of packets that are missing (not actually listed in Table 1)
• Asymmetric routing (6 metrics)

  1. flow type (two-way CSC, one-way client-to-server C2S, or one-way server-to-client S2C)
  2. inconsistent TTL
  3. number of inspection points when asymmetric traffic is correlated
  4. number of data centers when asymmetric traffic is correlated
  5. number of area addrs when asymmetric traffic is correlated(?)
  6. number of ISPs when asymmetric traffic is correlated

The measurement system uses DPDK for high-speed packet processing and Apache Kafka and Apache Spark for analysis. It runs on a cluster of 32 cores and 64 GB RAM total.

The results of the deployment experiment are not terribly interesting. There are, for example, stats on how many TCP segments contain data, how often packets are out of order, and how often flows exhibit inconsistent TTLs. The most involved part is what they call origin–destination flow measurement (Sections III-B.5 and V-G). This quantifies the degree of routing asymmetry pairwise between data centers. Fig. 15 shows empirical ratios across the experimental deployment in 6 data centers:

Don't mistake this figure for a diagram of network connectivity. It is not the case, for example, that DC1 is connected to DC2 and vice versa. Rather, a directed edge between DC_i and DC_j with weight w means that a w fraction of all flows seen by DC_i pass through DC_i in the upstream direction and DC_j in the downstream direction. When i ≠ j, the flows being considered are asymmetric. Here, for example, of all the flows seen by DC2, 20% have both the upstream and downstream passing through DC2, 9% have the upstream passing through DC2 and the downstream passing through DC1, 18% have upstream through DC2 and downstream through DC4, and 32% have upstream through DC2 and downstream unobserved (U). The numbers don't add to 100% because the total number of flows seen by DC2 also includes ones where only the downstream passes through DC2. To create such a diagram requires a global view of flows across data centers, and the ability to attribute different packets in different data centers as belonging to the same flow.

[wkrp]

This paper is closely related to another one published in the same year by the same authors.

Evaluating Routing Asymmetry by Passive Flow Measurements with Spark
刘军 (Liu Jun), 郑超 (Zheng Chao), 郭莉 (Guo Li), 刘学利 (Liu Xueli), 陆秋文 (Lu Qiuwen)
https://ieeexplore.ieee.org/document/8386552
PDF

It uses the same experiment across 6 data centers, some figures are similar or identical, and there are even passages of copy-pasted text. In comparison to "Network Traffic Constraints", "Evaluating Routing Asymmetry" has more of a focus on just the routing symmetry measurements.

[wkrp]

The reading group for "Understanding the Network Traffic Constraints" will begin 20 hours from now at 2023-08-20 13:00.

https://meet.jit.si/moderated/26537d37ba898afbe1d0f4a85d48ca282b84e5002a0db7ddc76fa1cf7ff893b7

I will open the call about 20 minutes early to give time for troubleshooting connection issues.

[wkrp]

Link to video

Links that were posted in the chat:

• 00:39: Discussion thread
• 00:42: Paper PDF
• 08:06: DPDK
• 27:47: Your State is Not Mine: A Closer Look at Evading Stateful Internet Censorship
• 31:16: Evaluating routing asymmetry by passive flow measurements with spark
• 42:22: Secure asymmetry and deployability for decoy routing systems

---

During the discussion we talked about how DPI middleboxes need to impose some kind of timeout or other resource limitation on flow tracking, in order to prevent the flow table from filling up with unterminated or misunderstood flows. I said I would look for some examples of research on limitations like these found in practice. One example is "Towards Illuminating a Censorship Monitor's Model to Facilitate Evasion":

…state management that will retain state for extensive periods of time (hours) but will discard state in lieu of very modest TCP bytestream buffering (1KB).

Due to resource constraints, any stateful monitor must define a policy for ultimately discarding state (for long-running connections), typically framed in terms of how long and/or how much state to keep. Inducing the monitor to discard state can then open up an evasion opportunity.

GFW's current design choice of keeping state for lengthy periods of time (except for connections with holes) renders it vulnerable to resource-exhaustion attacks.

"Your State is Not Mine" (which is cited in the reading group paper) has an example of a limitation in space, rather than time:

One can then craft insertion packets that contain junk data to fill the GFW’s receive buffer, while making them to be ignored by the server.

You also may want to look at the patent CN109672648 (English translation), the claimed invention of which is tuning flow-tracking timeouts according to the application protocol. The patent CN109672701 does something similar with application protocol–specific reassembly buffer sizes.

Protocol Type	Protocol Category	Recommended timeout
TELNET	Remote Management	300 s
RTMP	Audio and Video	30 s
QQ	Chat Tool	600 s
FTP-data link	File Transfer	10 s

---

A question came up during the discussion, asking for more background on the "origin–destination flow" concept of Section III-B (page 3, item 5). I looked a little more into it, and my impression is that this paper is misusing the term. Origin–destination flow seems to be a pretty well-established concept. For example, the U.S. census publishes commuting data in origin–destination format. It's a topic in transportation and networking. The usual way to express such information is as a matrix with integer counts. This paper instead expresses the relationship between a pair of nodes as a fraction, but as we discussed in the reading group, because of the way they define it, the fractions don't quite add up. It's also a strain of the terminology, because the entries in their graphs/matrices don't have anything directly to do with the origin and destination of the flows they are measuring. They are indeed relations between nodes (the nodes, in this case, being network monitors installed in data centers), but they are not "origin–destination" relations. More like "upstream–downstream" relations.

Here's an example of how the origin–destination matrix is a little weird. This is the RelationshipSet matrix (Eq. (2)) that would correspond to the graph in Fig. 15:

	DC1	DC2	DC3	DC4	DC5	DC6	U
DC1	0.053	0.08	-	-	-	-	0.256
DC2	0.09	0.2	-	0.18	-	-	0.32
DC3	-	-	0.78	-	-	-	0.14
DC4	-	-	-	0.23	-	-	0.145
DC5	0.024	-	-	-	0.295	-	0.285
DC6	0.005	-	-	-	0.027	0.36	0.546
U	0.43	0.09	0.07	0.52	0.35	0.04	-

Take the second row, for example. That's all the flows which DC2 saw in the upstream direction, and some other node (or even DC2 itself) saw in the downstream direction. Adding them up, we get 0.09 + 0.2 + 0.18 + 0.32 = 0.79. The second column is all the flows that DC2 saw in the downstream direction. Adding up the column, we get 0.08 + 0.2 + 0.9 = 0.37. Even if we add the row and column sums together, taking care not to count DC2 itself twice, we get 0.96. Because every row uses a different denominator, things don't add up in general.

[cohosh]

Thank you for summarizing the discussion! I want to add a few notes on routing asymmetry that I came across when looking into this a few years ago.

Filtering out one-way traffic with no data seems to be common practice in these kinds of passive measurement studies of traffic characteristics. Many will only consider TCP packets without the signaling flags SYN, RST, and FIN but with ACK, so that connections without data are discarded. This filtered traffic is typically classified as Internet background radiation (and backscatter that results from hosts responding to it). This, admittedly old, study found that of Internet background radiation, the vast majority of the packets were TCP SYN packets[0], and the backscatter is mostly SYN-ACK and RST packets. My understanding is that the levels of background radiation are pretty high in general and the 70% number isn't necessarily unusual, but without more information on where these probes occurred I guess it's hard to tell.

That 90% of the connections were asymmetric matches some previous results. A study called "Estimating Routing Symmetry on Single Links by Passive Flow Measurements" passively collected data between 2006 and 2009[1]. The experimental methods are somewhat similar to the discussed research in that the measurements were passively collected. The most interesting insight to me was how the proportion of asymmetric traffic is dependent on where the data is collected. This intuitively makes sense: the closer the backbone you are, the more likely traffic will take a different route to and from the destination, and the closer you get to either endpoint the fewer options there are and the more symmetric the routes become. The 2006-2009 study collected from 4 different locations with the percentage of asymmetric 5-tuple flows summarized as follows:

Location	% asymmetric
Tier-2	~30%
Tier-1 to Tier-2 link	~90%
Tier-1	~95%

I'm hesitant to over apply the results of a single study performed over 15 years ago, but the data presented here on the percentage of routes that are asymmetric and the levels of Internet background radiation are almost certainly leaking something about the Internet topology of where they conducted their experiments. I wonder if there are some interesting experiments that could be done that leverage the limitations of route asymmetry on traffic filtering to learn more about the Internet topologies of censorship deployments.

The most surprising result for me from this paper was the missing and out-of-order packet counts. The paper "Characterizing Transnational Internet Performance and the Great Bottleneck of China"[2] measures a daily packet loss rate for traffic between China and the US to be around 5-15%, but heavily dependent on the time of day and only affecting ingress traffic. It's possible the studies were conducted on a link that mostly carries domestic traffic or during the night when the load and packet loss rates are much lower, but I'd assume if they are performing these studies for the purpose of assessing limitations of DPI for censorship purposes, then peak load times and transnational links would be exactly those that they care about.

[0] https://dl.acm.org/doi/10.1145/1028788.1028794 (PDF)
[1] https://dl.acm.org/doi/10.1145/1815396.1815506 (PDF)
[2] https://censorbib.nymity.ch/#Zhu2020a

[wkrp]

My understanding is that the levels of background radiation are pretty high in general and the 70% number isn't necessarily unusual, but without more information on where these probes occurred I guess it's hard to tell.

I see, maybe my interpretation was wrong. I interpreted the 70% figure to mean 70% of packets in otherwise data-carrying flows; you're saying that it may be more like 70% of flows (if we count a port scan's SYN→SYNACK→RST as one flow).

In experiment, we find that there is a large amount of TCP traffic without data and account for more than 70% of client-to-server (C2S) traffic, as illustrated in Fig.8.

The most surprising result for me from this paper was the missing and out-of-order packet counts.

They report higher rates of duplicate packets than missing packets. Is it true that duplicate packets would usually indicate packet loss somewhere else in the path? Maybe that helps account for the lower-than-expected rate of missing packets.

As shown in Fig.9, on average, less than 7% of TCP flow has loss packet in six data centers. As is show in Fig.10, more than 90% of TCP flow out of sequence. Moreover, the average ratio of out-of-order packet is less than 20%. It suggests that the phenomenon of out-of-order is pervasive in ISPs network but the condition of out-of-order packet is not very serious. And as shown in Fig.11, we find that the average flow ratio of c2s directional retransmission is higher than of s2c directional retransmission.

[cohosh]

I see, maybe my interpretation was wrong. I interpreted the 70% figure to mean 70% of packets in otherwise data-carrying flows; you're saying that it may be more like 70% of flows (if we count a port scan's SYN→SYNACK→RST as one flow).

I think that's right, that it is 70% of connections, although I agree the wording is ambiguous. I did some more digging to see if I could find recent studies on the prevalence of IBR, but all I found were vague references to how the levels are high and more than half of Internet connections are scans. Most studies on IBR use telescopes that only look at traffic to unused address space so they're mostly useful for characterizing IBR not determining how much of Internet traffic is IBR.

They report higher rates of duplicate packets than missing packets. Is it true that duplicate packets would usually indicate packet loss somewhere else in the path? Maybe that helps account for the lower-than-expected rate of missing packets.

Yes you're right. These duplicate packets probably had higher sequence numbers than the dropped packets and so were retransmitted along with them. Looking at their methodology more closely:

For the processing performance of network traffic, we
compare the current sequence number and previous sequence
number of a packet for computing the number of duplicate
packets and out-of-order packets. And we set adequate buffers
to cache current several network packets for computing missing
packets.

This is too vague, but my guess is that these buffers were large enough that TCP retransmitted the dropped packets and they characterized the traffic as out-of-order rather than missing.

Looking at the out-of-order numbers again, if a good portion of that 20% rate of occurrence is due to retransmittted packets this makes a lot more sense.

[wkrp]

During the discussion we talked about how DPI middleboxes need to impose some kind of timeout or other resource limitation on flow tracking, in order to prevent the flow table from filling up with unterminated or misunderstood flows. I said I would look for some examples of research on limitations like these found in practice.

Another paper on the subject of out-of-order data and reassembly buffer size from 2012:

A Dynamic Strategy to Cache Out-of-Sequence Packet in DPI System
PDF

As a major approach for a network security system to discover threats or forensics, DPI (Deep Packet Inspection) technique is widely used in monitoring network flow. With the rapid development of Internet bandwidth, DPI system is facing more and more challenges on performance. One of these challenges is that out-of-sequence packets in TCP transmission will greatly affect memory consumption and data-recall. For a large scale DPI system, each DPI node has to monitor a huge amount of TCP session. It will consume too many resources to allocate plenty of space for storing all out-of-sequence packets. Meanwhile, insufficient space for buffer results in dropping packets and thus unable to reassemble network flow. We analyze the out-of-sequence characteristic of different Internet flow, and implement a dynamic strategy to cache out-of-sequence packet, which provide a more flexible way to keep track of the sessions. Experiment shows that based on the new strategy, a DPI system can greatly improve the completeness of data recall with little extra consumption of space.