use std::collections::HashMap;
use std::fmt;
use std::time::Duration;
use crate::sparse::{Gap, Run, Sparse};
use crate::{Flow, Packet, Transport};
#[derive(Clone)]
pub struct Stream {
flow: Flow,
first_seen: Duration,
from_connection_start: bool,
bytes: Sparse,
}
impl Stream {
pub fn flow(&self) -> Flow {
self.flow
}
pub fn first_seen(&self) -> Duration {
self.first_seen
}
pub fn from_connection_start(&self) -> bool {
self.from_connection_start
}
pub fn runs(&self) -> &[Run] {
self.bytes.runs()
}
pub fn contiguous(&self) -> Option<&[u8]> {
self.bytes.contiguous()
}
pub fn gaps(&self) -> Vec<Gap> {
self.bytes.gaps()
}
pub fn len(&self) -> u64 {
self.bytes.len()
}
pub fn is_empty(&self) -> bool {
self.bytes.is_empty()
}
}
impl fmt::Debug for Stream {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_struct("Stream")
.field("flow", &self.flow)
.field("bytes", &self.len())
.field("runs", &self.runs().len())
.field("from_connection_start", &self.from_connection_start)
.finish_non_exhaustive()
}
}
#[derive(Debug, Default)]
pub struct Reassembler {
ports: Option<Vec<u16>>,
flows: HashMap<Flow, Builder>,
order: u64,
}
impl Reassembler {
pub fn new() -> Self {
Self {
ports: None,
flows: HashMap::new(),
order: 0,
}
}
pub fn on_ports(ports: impl IntoIterator<Item = u16>) -> Self {
Self {
ports: Some(ports.into_iter().collect()),
flows: HashMap::new(),
order: 0,
}
}
pub fn push(&mut self, packet: &Packet) {
let Transport::Tcp { sequence, syn, .. } = packet.transport else {
return;
};
let flow = Flow::of(packet);
if let Some(ports) = &self.ports
&& !ports.iter().any(|&port| flow.involves(port))
{
return;
}
if !syn && packet.payload.is_empty() {
return;
}
self.remember(flow, packet.timestamp);
let Some(builder) = self.flows.get_mut(&flow) else {
return;
};
if syn {
builder.open(sequence.wrapping_add(1));
}
if !packet.payload.is_empty() {
let start = if syn {
sequence.wrapping_add(1)
} else {
sequence
};
builder.add(start, &packet.payload);
}
}
fn remember(&mut self, flow: Flow, timestamp: Duration) {
if self.flows.contains_key(&flow) {
return;
}
let order = self.order;
self.order = self.order.saturating_add(1);
self.flows.insert(
flow,
Builder {
flow,
first_seen: timestamp,
base: None,
from_connection_start: false,
bytes: Sparse::new(),
order,
},
);
}
pub fn finish(self) -> Vec<Stream> {
let mut builders: Vec<Builder> = self
.flows
.into_values()
.filter(|builder| !builder.bytes.is_empty())
.collect();
builders.sort_by_key(|builder| builder.order);
builders
.into_iter()
.map(|builder| Stream {
flow: builder.flow,
first_seen: builder.first_seen,
from_connection_start: builder.from_connection_start,
bytes: builder.bytes,
})
.collect()
}
}
#[derive(Debug)]
struct Builder {
flow: Flow,
first_seen: Duration,
base: Option<u32>,
from_connection_start: bool,
bytes: Sparse,
order: u64,
}
impl Builder {
fn open(&mut self, base: u32) {
self.from_connection_start = true;
self.rebase(base);
}
fn add(&mut self, sequence: u32, data: &[u8]) {
let base = *self.base.get_or_insert(sequence);
let delta = sequence.wrapping_sub(base);
if delta & 0x8000_0000 == 0 {
self.bytes.insert(u64::from(delta), data);
} else {
self.rebase(sequence);
self.bytes.insert(0, data);
}
}
fn rebase(&mut self, base: u32) {
match self.base {
None => self.base = Some(base),
Some(current) => {
let shift = current.wrapping_sub(base);
if shift == 0 || shift & 0x8000_0000 != 0 {
return; }
self.bytes.shift(u64::from(shift));
self.base = Some(base);
}
}
}
}
#[cfg(test)]
mod tests {
use std::net::{Ipv4Addr, SocketAddrV4};
use super::*;
fn endpoint(last_octet: u8, port: u16) -> SocketAddrV4 {
SocketAddrV4::new(Ipv4Addr::new(169, 254, 0, last_octet), port)
}
struct Wire {
index: u64,
}
impl Wire {
fn new() -> Self {
Self { index: 0 }
}
fn segment(&mut self, from: u16, to: u16, sequence: u32, payload: &[u8]) -> Packet {
self.build(from, to, sequence, payload, false)
}
fn syn(&mut self, from: u16, to: u16, sequence: u32) -> Packet {
self.build(from, to, sequence, b"", true)
}
fn build(
&mut self,
from: u16,
to: u16,
sequence: u32,
payload: &[u8],
syn: bool,
) -> Packet {
self.index += 1;
Packet {
index: self.index,
timestamp: Duration::from_millis(self.index),
interface: 0,
source: endpoint(1, from),
destination: endpoint(2, to),
transport: Transport::Tcp {
sequence,
syn,
fin: false,
reset: false,
},
payload: payload.to_vec(),
}
}
}
fn reassemble(packets: &[Packet]) -> Vec<Stream> {
let mut reassembler = Reassembler::new();
for packet in packets {
reassembler.push(packet);
}
reassembler.finish()
}
#[test]
fn segments_in_order_become_one_stream() {
let mut wire = Wire::new();
let packets = [
wire.segment(1053, 1051, 100, b"hello "),
wire.segment(1053, 1051, 106, b"world"),
];
let streams = reassemble(&packets);
assert_eq!(streams.len(), 1);
assert_eq!(
streams.first().and_then(Stream::contiguous),
Some(b"hello world".as_slice())
);
}
#[test]
fn the_two_directions_are_separate_streams() {
let mut wire = Wire::new();
let mut request = wire.segment(1053, 1051, 100, b"request");
let mut reply = wire.segment(1053, 1051, 0, b"reply");
std::mem::swap(&mut reply.source, &mut reply.destination);
request.timestamp = Duration::from_millis(1);
reply.timestamp = Duration::from_millis(2);
let streams = reassemble(&[request, reply]);
assert_eq!(
streams.len(),
2,
"interleaving the directions would invent a byte stream"
);
assert_eq!(
streams.first().and_then(Stream::contiguous),
Some(b"request".as_slice())
);
assert_eq!(
streams.get(1).and_then(Stream::contiguous),
Some(b"reply".as_slice())
);
assert_eq!(
streams.first().map(|stream| stream.flow().reversed()),
streams.get(1).map(Stream::flow)
);
}
#[test]
fn a_missing_segment_is_reported_not_concatenated_over() {
let mut wire = Wire::new();
let packets = [
wire.segment(1053, 1051, 100, b"first "),
wire.segment(1053, 1051, 112, b"third "),
];
let streams = reassemble(&packets);
let stream = streams.first().expect("one stream");
assert_eq!(
stream.contiguous(),
None,
"a dbserver reader given `first third ` would decode confident nonsense"
);
assert_eq!(stream.gaps(), vec![Gap { offset: 6, len: 6 }]);
assert_eq!(stream.runs().len(), 2);
assert_eq!(stream.len(), 12);
}
#[test]
fn a_retransmission_leaves_the_stream_unchanged() {
let mut wire = Wire::new();
let packets = [
wire.segment(1053, 1051, 100, b"hello "),
wire.segment(1053, 1051, 106, b"world"),
wire.segment(1053, 1051, 100, b"hello "),
wire.segment(1053, 1051, 106, b"world"),
];
let streams = reassemble(&packets);
assert_eq!(
streams.first().and_then(Stream::contiguous),
Some(b"hello world".as_slice())
);
assert_eq!(streams.first().map(Stream::len), Some(11));
}
#[test]
fn out_of_order_segments_are_put_back_in_order() {
let mut wire = Wire::new();
let packets = [
wire.segment(1053, 1051, 106, b"world"),
wire.segment(1053, 1051, 100, b"hello "),
];
let streams = reassemble(&packets);
assert_eq!(
streams.first().and_then(Stream::contiguous),
Some(b"hello world".as_slice())
);
assert_eq!(
streams.first().map(Stream::from_connection_start),
Some(false),
"no SYN was captured, so the start of the connection is unknown"
);
}
#[test]
fn a_sequence_number_wrapping_past_zero_is_not_a_hole() {
let mut wire = Wire::new();
let packets = [
wire.segment(1053, 1051, 0xffff_fffc, b"abcd"),
wire.segment(1053, 1051, 0, b"efgh"),
];
let streams = reassemble(&packets);
let stream = streams.first().expect("one stream");
assert_eq!(stream.contiguous(), Some(b"abcdefgh".as_slice()));
assert!(stream.gaps().is_empty());
}
#[test]
fn the_syn_does_not_consume_a_payload_byte() {
let mut wire = Wire::new();
let packets = [
wire.syn(1053, 1051, 4242),
wire.segment(1053, 1051, 4243, b"first byte is here"),
];
let streams = reassemble(&packets);
let stream = streams.first().expect("one stream");
assert!(stream.from_connection_start(), "the SYN was captured");
assert_eq!(stream.contiguous(), Some(b"first byte is here".as_slice()));
assert!(
stream.gaps().is_empty(),
"a SYN numbers itself, not a byte of data"
);
}
#[test]
fn a_capture_that_starts_mid_connection_says_so() {
let mut wire = Wire::new();
let packets = [wire.segment(1053, 1051, 900_000, b"midstream")];
let streams = reassemble(&packets);
let stream = streams.first().expect("one stream");
assert!(!stream.from_connection_start());
assert_eq!(
stream.contiguous(),
Some(b"midstream".as_slice()),
"offset zero is the earliest byte seen, not the connection's first"
);
}
#[test]
fn a_handshake_that_carried_nothing_is_not_a_stream() {
let mut wire = Wire::new();
let packets = [wire.syn(1053, 1051, 7)];
assert!(reassemble(&packets).is_empty());
}
#[test]
fn a_udp_packet_is_not_offered_to_a_stream() {
let mut wire = Wire::new();
let mut packet = wire.segment(1053, 1051, 0, b"not tcp");
packet.transport = Transport::Udp;
assert!(reassemble(&[packet]).is_empty());
}
#[test]
fn a_port_filter_matches_either_endpoint() {
let mut wire = Wire::new();
let to_server = wire.segment(1053, 1051, 0, b"query");
let mut from_server = wire.segment(1051, 1053, 0, b"answer");
std::mem::swap(&mut from_server.source, &mut from_server.destination);
let elsewhere = wire.segment(2049, 2049, 0, b"nfs");
let mut reassembler = Reassembler::on_ports([1051]);
for packet in [&to_server, &from_server, &elsewhere] {
reassembler.push(packet);
}
let streams = reassembler.finish();
assert_eq!(
streams.len(),
2,
"a connection's two directions both belong to its port"
);
}
#[test]
fn the_same_segment_seen_on_two_interfaces_is_one_copy_of_the_bytes() {
let mut wire = Wire::new();
let first = wire.segment(1053, 1051, 100, b"once");
let mut duplicate = first.clone();
duplicate.interface = 1;
let streams = reassemble(&[first, duplicate]);
assert_eq!(streams.len(), 1);
assert_eq!(
streams.first().and_then(Stream::contiguous),
Some(b"once".as_slice())
);
}
}