# FEAROL: Aging Flow Entries Based on Local Staircase Randomized Response for Secure SDN Flow Tables
## 2 Background and Related Work
### Randomized Response  
Randomized response is a data perturbation mechanism introduced by [PERSON] (1986) and is widely used in local differential privacy. Differential privacy provides a strong criterion for privacy preservation ([PERSON] _et al._, 2011). Differential privacy mechanisms can be centralized or localized. Centralized mechanisms require a trusted third party to collect the private data before distributing the randomized response; however, a fully trusted third party is hardly achievable in reality. Local differential privacy mechanisms address this problem by perturbing private data locally. A differential privacy method \(M\) has a privacy budget \(\epsilon\) if two records of \(t\) and \(t^{{}^{\prime}}\) have the same output of \(t^{*}\) (\(t^{*}\) is in the range of \(M\)) and make the following statement true.  
\[Pr[M(t)=t^{*}]>\epsilon^{\epsilon}*Pr[M(t^{{}^{\prime}})=t^{*}] \tag{1}\]  
Randomized response is widely used to perturb binary data in local differential privacy. The basic idea is to make the \"true\" statement with some probability \(p\) less than \(1\) and with probability of \(1-p\) otherwise. Consider a survey with \(n\) users being surveyed: the true ratio of users answering \"yes\" is \(\pi\), which is not known and is estimated through the survey. Suppose \(n1\) users answer \"yes\" and \(n-n1\) users answer \"no\", then the probability of users answering \"yes\" and \"no\" can be computed by Equations (2) and (3), respectively, and Equations (4) and (5) represent the likelihood function \(L\) and the estimated maximum likelihood, respectively. The expectation of \(\pi^{-}\) is \(\pi\) as computed by Equation (6). \(\pi^{-}\) is the unbiased estimate of \(\pi\), and the privacy budget \(\epsilon\) can be calculated using Equation (7) ([PERSON] _et al._, 2011). All symbols are listed in Table 2.  
\[Pr(\textit{answer \"yes}^{\prime})=\pi p+(1-\pi)(1-p) \tag{2}\]  
\[Pr(\textit{answer \"no\"})=(1-\pi)p+\pi(1-p) \tag{3}\]  
\[L=[\pi p+(1-\pi)(1-p)]^{n1}[(1-\pi)p+\pi(1-p)]^{n-n1} \tag{4}\]  
\[\pi^{-}=(p-1)/(2p-1)+n1/[(2p-1)n] \tag{5}\]  
\[E(\pi^{-})=1/(2P-1)[P-1+\pi p+(1-\pi)(1-p)]=\pi \tag{6}\]  
Figure 3: Flow table overflow LDoS attacks in SDN systems.  
\[\epsilon=lnp/(1-p) \tag{7}\]  
Since randomized response only considers binary data, two typical approaches are used to extend it to scenarios with discrete data: (1) encoding or converting the response to binary and (2) adjusting the probability distribution of all responses. While RAPPOR [43] and S-Hist [44] are the typical mechanisms of (1), staircase randomized response mechanisms, such as k-RR [15] and O-RR [16] are the representations of (2).  
Regarding the staircase randomized response, let \(R^{{}^{\prime}}\) be the response of each input \(R\), then we have Equations (8) and (9) in the privacy budget \(\epsilon\)[15]. This work does not make surveys over perturbed answers as most of the approaches have been conducted but instead incorporates the staircase randomized response in the flow-entry-aging process to randomize the lifespans of flow entries within a privacy budget so that the real lifespans of flow entries are unknown, and the sniffed flow-entry timeouts are useless for flow table overflow LDoS attacks.  
\[Pr(R^{{}^{\prime}}=R|R)=e^{\epsilon}/(k-1+e^{\epsilon}) \tag{8}\]  
\[Pr(R^{{}^{\prime}}\
eq R|R)=1/(k-1+e^{\epsilon}) \tag{9}\]