Flow reconnaissance via timing attacks on SDN switches

When encountering a packet flow for which it has no covering rule, a software-defined networking (SDN) switch requests an appropriate rule from its controller; this request delays the routing of the flow until the controller responds. We show that this delay gives rise to a timing side channel in which an attacker can test for the recent occurrence of a target flow by judiciously probing the switch with forged flows and using the delays they suffer to discern whether covering rules were previously installed in the switch. We develop a Markov model of an SDN switch to permit the attacker to select the best probe (or probes) to infer whether a target flow has recently occurred. Our model captures complexities related to rule evictions to make room for other rules; rule timeouts due to inactivity; the presence of multiple rules that apply to overlapping sets of flows; and rule priorities. We show that our model permits detection of target flows with considerable accuracy in many cases.