# Flow Table Saturation Attack against Dynamic Timeout Mechanisms in SDN
## 4 Improved Saturation Attack Method
### The Triggering Phase
#### 4.4.2 Adaptive Timeouts  
For the adaptive timeout strategy, the attacker needs to use multiple rounds of probing and generate attack flows with specified patterns to force the assignment of large timeouts. One of the main challenges is that the detailed logic of assigning timeouts deployed on the control plane is agnostic to the attacker. To address this, we analyze the basic logic of the adaptive timeout mechanisms and summarize their common features as follows:  
1. **Lightweight**. Timeout decision is a part of the packet-in message process. It must achieve quick response and incur low storage overhead. 2. **Small initial value**. Since most flows are short-lived, a new flow rule always starts with a low timeout value. 3. **Timeout increment**. The calculated timeout is expected to cover the packet intervals. Since the primary function of the adaptive timeout mechanism is to reduce the number of packet-in events, the controller should set larger values for rules due repeated table-miss events. 4. **Maximum limitation**. Too large a timeout can result in wasted flow table space. Generally, an upper bound is set to prevent the infinite increase in timeouts. 5. **Timeout decreased**. Flows with too-large packet intervals will not be assigned with large timeout values. For mice flows with a very large packet inter-arrival time, when receiving a packet-in long after the flow rule is expired, the timeout should be decreased, or even set to the initial value. Based on the summary, the timeout value becomes predictable. The maximum timeout in most adaptive timeout mechanisms is usually less than 15 s [15; 28], and the OpenFlow protocol only accepts integer timeouts in seconds. Thus, we can model the timeout value of flow rules using a finite-state machine (FSM). Here, the state of the flow rules is its idle timeout value. The initial timeout value is the initial state, and the target value (\(T_{f}\)) can be the end state. Since only an unmatched packet can cause the new rule installation with a newly calculated timeout (i.e., state transition), the transition actions are triggered by the packets that are sent after the flow rule expires. The state transition is determined by the time interval between the last hit time of the flow rule and the probing packet that triggers the table-miss. When reaching a certain state, we send a probing packet with a packet interval larger than its timeout value as an action. To obtain the new state (output), we can use the _search_timeout_ operation to infer its exact timeout value. In this way, a transition path between the two states is constructed. Then. we change the packet header fields, generate another flow and transit the corresponding flow rule state to this state. By repeating the process, we can find the transition paths from this state to other states. Figure 6 gives an example. The packet interval time is presented above the arrow. However, the _search_timeout_ operation needs multiple rounds of probing, which is time-consuming. To make it simpler, we can perform the _compare_timeout_ operation to acquire the 'coarse state' instead. The key point is that when a new timeout is calculated, we only need to infer whether it is larger than the previous value. After a flow rule is deployed, we send a probing packet with a packet interval slightly larger than its timeout to deliberately trigger a new rule installation. Since the reinstallation event occurs soon after the flow rule expires, we can prevent the **\"timeout reduction\"** condition. Then, we wait for the same time and send a testing packet to measure whether it can be matched by the new rule. If it hits, it indicates that the timeout is larger than the previous one and can cover the packet interval, which is the **\"timeout increment\"** condition. Otherwise, we can conclude the controller limits the timeout increase (i.e., the **\"maximum limitation\"**). We plot the process in Figure 7 to give a detailed example. The dotted arrow indicates that the packet triggers a table-miss.