# All Graphs with at most 8 nodes are $2$-interval-PCGs

###### Abstract

A graph $G$ is a multi-interval PCG if there exist an edge weighted tree $T$
with non-negative real values and disjoint intervals of the non-negative real
half-line such that each node of $G$ is uniquely associated to a leaf of $T$
and there is an edge between two nodes in $G$ if and only if the weighted
distance between their corresponding leaves in $T$ lies within any such
intervals. If the number of intervals is $k$, then we call the graph a
$k$-interval-PCG; in symbols, $G=$ $k$-interval-PCG $(T,I_{1},\ldots,I_{k})$.

It is known that $2$-interval-PCGs do not contain all graphs and the smallest
known graph outside this class has 135 nodes. Here we prove that all graphs
with at most 8 nodes are $2$-interval-PCGs, so doing one step towards the
determination of the smallest value of $n$ such that there exists an $n$ node
graph that is not a $2$-interval-PCG.

T. Calamoneri A. Monti F. Petroni
Sapienza University of Rome - Computer Science Department, Italy

keywords:  Pairwise Compatibilty Graphs; Multi-Interval PCGs.

##  1 Introduction

A graph $G=(V,E)$ is a pairwise compatibility graph (PCG) if there exist an
edge-weighted tree $T$ with non-negative real values and an interval $I$ of
the non-negative real half-line such that each node $u\in V$ is uniquely
associated to a leaf of $T$ and there is an edge $(u,v)\in E$ if and only if
$d_{T}(u,v)\in I$, where $d_{T}(u,v)$ is the weighted distance between the
leaves associated to $u$ and $v$ in $T$. In such a case, we say that $G$ is a
PCG of $T$ for $I$; in symbols, $G=PCG(T,I)$.

The concept of pairwise compatibility was introduced in [10] in a
computational biology context and it was conjectured that every graph is a
PCG. The conjecture has then been confuted in [14], where the first examples
of graphs that are not PCGs were provided. Since then, much work has been done
in order to understand which graphs are PCGs (e.g. see the surveys [8, 13]).

Knowing that not all graphs are PCGs, a natural generalization of PCGs has
been introduced in [1]: a graph $G$ is a multi-interval PCG if there exists an
edge-weighted tree $T$ with non-negative real values and disjoint intervals of
the non-negative real half-line such that each node of $G$ is uniquely
associated to a leaf of $T$ and there is an edge between two nodes in $G$ if
and only if the weighted distance between their corresponding leaves in $T$
lies within any such intervals. If the number of intervals is $k$, then we
call the graph a $k$-interval-PCG; in symbols, $G=$ $k$-interval-PCG
$(T,I_{1},\ldots,I_{k})$.

When $k=1$, the $1$-interval-PCG class coincides with the PCG class. Instead,
already when $k=2$ the graph class of PCGs is strictly contained in the graph
class of $2$-interval-PCGs; indeed, there exist graphs that are not PCGs but
are $2$-interval-PCGs: the smallest such graph has 8 nodes [9]; other graphs
that are not in PCG but are in $2$-interval-PCG are wheels (i.e., one
universal node connected to all the nodes of a cycle) with at least 9 nodes
and a restricted subclass of series-parallel graphs [1].

It is also known that $2$-interval-PCGs do not contain all graphs and the
smallest known graph outside this class has 135 nodes [7]. A natural question
is which is the smallest value of $n$ such that there exists an $n$ node graph
that is not a $2$-interval-PCG. In this paper, we make one step in this
direction: it is known that all graphs with at most 7 nodes are PCGs [5] and
hence $2$-interval-PCGs; here we show that all graphs with 8 nodes are
$2$-interval-PCGs, and to do it, it is enough to focus on the 8 node graphs
that are not PCGs. Note that we are working analogously as for PCGs. Indeed,
the first graph recognized to be outside the PCG class had 15 nodes [14]; in
order to find the smallest graph not in PCG, Phillips [12] first proved in an
exhaustive way that all graphs with less than five nodes are PCGs, then the
result was extended to all graphs with at most seven nodes [5] and later to
all bipartite graphs on eight nodes [11]. Finally, Durocher, Mondal, and
Rahman [9] proved that there exists a graph with 8 nodes that is not a PCG.

There exist only seven graphs $G_{1},\ldots G_{7}$ with 8 nodes that are not
PCGs [2] and are depicted in Figure 1. Only $G_{1}$ is already known to be in
$2$-interval-PCG [7]; here we prove that all the others are $2$-interval-PCGs
as well. In fact, our result is summarized in Figure 2, and the rest of the
paper is needed to justify this figure. More in detail, this paper is
organized as follows: in Section 2 we prove some sufficient conditions for a
graph to be in $2$-interval-PCG, and we exploit them to prove that $G_{4}$,
$G_{6}$ and $G_{7}$ are $2$-interval-PCGs; in Section 3 we generalize some
results proved for PCGs to let them work for $2$-interval-PCGs, too, and we
exploit an ILP model to determine whether a given graph ia a $2$-interval-PCG
with respect to a given tree structure; from it, we deduce that the remaining
8 node graphs are $2$-interval-PCGs. Finally, we are able to find witness
trees and intervals for all the graphs in Figure 1; we show them in Figures 2
and 3, observing that they have all the same structure (either complete binary
tree or caterpillar). Section 4 concludes the paper.

Figure 1: The seven graphs with 8 nodes that are not PCGs.

##  2 $G_{4}$, $G_{6}$ and $G_{7}$ are $2$-interval-PCGs.

To show that graphs $G_{4}$, $G_{6}$ and $G_{7}$ of Figure 1 are $2$-interval-
PCGs, we prove two theorems giving sufficient conditions for a graph to be a
$2$-interval-PCG.

Let $G$ be a graph, a universal node for $G$ is a node that is adjacent to all
other nodes of $G$; a node is almost universal for $G$ if it is adjacent to
all the nodes in $G$ but one.

We now prove the following general result.

###### Theorem 1

Let $G$ be a graph with a universal node $u$. If the subgraph $G^{\prime}$ of
$G$, obtained from $G$ by removing $u$, is PCG, then $G$ is a $2$-interval-
PCG.

Proof. Let $G^{\prime}=PCG(T,I)$ with $I=[a,b]$. We construct a new tree
$T_{1}$ adding to the tree $T$ a leaf corresponding to $u$ and define a new
interval $I_{1}$ such that $G=PCG(T_{1},I,I_{1})$.

Let $p$ be the maximum distance between the leaves of $T$ (note that it is not
restrictive to assume that $b\leq p$). We construct $T_{1}$ by adding to $T$
the new leaf corresponding to $u$ as a child of an internal node $x$ of $T$
and edge $(x,u)$ in $T_{1}$ is assigned a weight $p+1$.

First note that leaf $u$ in $T_{1}$ has a distance at least $p+1$ from all the
other leaves of $T_{1}$ and no larger than $2p+1$.

We set $I_{1}=[p+1,2p+1]$ and observe that $I$ and $I_{1}$ are disjoint. It is
easy to see that $G$ coincides with $2$-interval-PCG$(T_{1},I,I_{1})$, that is
$G$ is in $2$-interval-PCG. $\Box$

Note that node 4 in graphs $G_{6}$ and $G_{7}$ in Figure 1 is a universal node
and their subgraphs obtained deleting it has seven vertices and are hence PCGs
(see [5]). The next result straightforwardly follows from this observation and
from Theorem 1:

###### Corollary 1

Non PCG graphs $G_{6}$ and $G_{7}$ are in $2$-interval-PCG.

In order to handle graph $G_{4}$, we prove the following general result.

###### Theorem 2

Let $G$ be a graph with an almost universal node $u$. If the subgraph
$G^{\prime}$ of $G$, obtained from $G$ by removing $u$, is PCG, then $G$ is a
$2$-interval-PCG.

Proof. Let $G^{\prime}=PCG(T,I)$ with $I=[a,b]$. Starting from tree $T$ we now
create a new tree $T_{1}$ by adding a weight $2$ to all the edges of $T$
incident to the leaves. In this way, the distances between any two leaves in
$T$ are augmented by exactly $4$ in $T_{1}$ and hence
$G^{\prime}=PCG(T_{1},I_{1})$ where $I_{1}=[a+4,b+4]$ and the weight of each
edge incident to a leaf is strictly larger than 1.

Let $v$ be the only node not connected with the almost universal node $u$ of
$G$, and let $x$ be the parent of leaf $v$ in $T_{1}$; call $c$ the weight of
edge $(v,x)$ in $T_{1}$. (Note that $c\geq 2$ because we are in $T_{1}$.) Now
construct a new tree $T_{2}$ obtained from $T_{1}$ deleting edge $(v,x)$ and
adding a dummy internal node $y$ connected with $v$ and $x$, where edge
$(v,y)$ has weight $1$ and edge $(y,x)$ has weight $c-1$. Obviously, again
$G^{\prime}=PCG(T_{2},I_{1})$.

Let $p$ be the maximum distance between the leaves of $T_{2}$ and hence it is
not restrictive to assume that the right extreme of $I_{1}$ is $b+4\leq p$.
Finally construct $T_{3}$ adding to $T_{2}$ new leaf $u$ connected to $y$ with
an edge of weight $p$. Note that $u$ has distance $p+1$ from $v$ in $T_{3}$.
Moreover, the distance in $T_{3}$ between $u$ and any other leaf is less than
$2p$ and at least $p+2$. Indeed, the weight of edge $(u,y)$ is $p$ and the
weight of the unique incident edge of any other leaf is at least 2. So, we set
$I_{2}=[p+2,2p]$.

Easily $I_{1}$ and $I_{2}$ are disjoint and $G=$ $2$-interval-
PCG$(T_{3},I_{1},I_{2})$ and hence it is a $2$-interval-PCG. $\Box$

Node 1 in graph $G_{4}$ of Figure 1 is an almost universal node and the
subgraph of $G_{4}$ obtained deleting this node is a PCG having seven nodes
[5]. So, by Theorem 2, we have the following result.

###### Corollary 2

Non PCG graph $G_{4}$ is $2$-interval-PCG.

##  3 $G_{2}$, $G_{3}$ and $G_{5}$ are $2$-interval-PCGs

In order to complete the proof that all graphs with at most 8 nodes are
$2$-interval-PCGs, we now generalize to $2$-interval-PCGs some known results
proved for PCGs in order to prove that all graphs with at most 7 nodes are
PCGs [4]. More precisely, Lemma 1 will allow us to check the $2$-interval-PCG
property of a graph only on a special tree structure instead of all possible
$n$ leaf trees; Lemma 2 will allow us to consider only integer edge-weights
and interval extremes instead of real values. The conjunction of these two
simplifications makes effective the ILP model we use to solve our problem.

A full binary tree is a tree whose all internal nodes, except for its root,
have a degree exactly 3.

A caterpillar is a tree for which any leaf is at a distance exactly one from a
central path called spine. Caterpillars as those depicted in Figure 3 are
special full binary trees (electing a leaf as root).

In [4] it is proved that, given any $n$ leaf tree $T$, there exists an edge-
weighted full binary tree $T^{*}$ on the same leaf set with the property that,
for any pair of leaves, their distance in $T$ and in $T^{\prime}$ is the same.

From this fact, the following result follows.

###### Lemma 1

Let $G$ be a $2$-interval-PCG; then there exists an edge-weighted full binary
tree $T^{*}$ and two disjoint intervals $I_{1}$ and $I_{2}$ such that $G=$
$2$-interval-PCG $(T^{*},I_{1},I_{2})$.

The following result, deduced from [6], allows us to use only integer values
both for the edge-weight function and for the extremes of the intervals.

###### Lemma 2

Let $G$ be a $2$-interval-PCG; then there exists an edge-weighted tree
$T^{\prime}$ with integer values and two disjoint intervals $I_{1}$ and
$I_{2}$ with integer extremes such that $G=$ $2$-interval-PCG
$(T^{\prime},I_{1},I_{2})$ and the tree structure does not change.

So, given a $2$-interval-PCG, Lemma 1 guarantees that one of its witness trees
is a full binary tree and Lemma 2 ensures that its edge-weight function and
the two interval use integer values.

In [4] an ILP model to determine whether a given graph is a PCG with respect
to a given tree structure is provided. More precisely, given a graph $G$ and
an unweighted tree $T$, the model determines (if they exist) an edge-weight
function $w$ for $T$, a bijective mapping $\sigma$ between the node set $V$ of
$G$ and the set of the leaves of $T$, and an interval $I$ of the non-negative
real half-line, such that $G=PCG(T^{\prime},I)$ where $T^{\prime}$ is the
edge-weighted tree obtained from $T$ introducing weight $w$ and mapping
$\sigma$. After this result, in other papers [2, 3] the ILP model has been
made more efficient, in order to work on larger graphs. Since we handle few
small graphs, here we adopt the first ILP model and opportunely modify it in
order to let it work for recognizing whether a graph belongs to the wider
class of $2$-interval-PCGs.

Note that we are able to exploit such an ILP model because the $2$-interval-
PCG property of a graph can be checked only on full binary trees instead of
all possible $n$ leaf trees and only for integer edge-weights and intervals
with integer extremes.

We apply this ILP model to $G_{2}$, $G_{3}$, and $G_{5}$ and get the following
result.

###### Corollary 3

Non PCG graphs $G_{2}$, $G_{3}$ and $G_{5}$ are $2$-interval-PCGs.

Since the solution of the ILP model produces an edge-weighted tree and two
intervals witnessing that the input graph is $2$-interval-PCG, we apply it to
all 7 graphs of Figure 1 with two special tree structures: complete binary
trees and caterpillars. In both cases, we obtain the witness edge-weighted
trees and the pairs of intervals for all the graphs: they are depicted in
Figures 2 and 3. This was not obvious, indeed in [5] the authors found that
all 7 node graphs are PCGs, all of them except one (the wheel) having as
witness tree a caterpillar.

Figure 2: The seven witness complete binary trees with 8 leaves and the
corresponding intervals.  Figure 3: The seven witness caterpillars with 8
leaves and the corresponding intervals.

##  4 Conclusions

It is known that all graphs with at most 7 nodes are PCGs and hence also
$2$-interval-PCGs. In this note, we proved that all 8 node graphs are
$2$-interval-PCGs.

We conclude by observing that 9 node graphs that are not PCGs are much more
than seven. In fact, in [3] only minimal PCGs (i.e., each of their induced
subgraphs is a PCG) with 9 nodes are enumerated and they are 1494. So, in
order to prove (or disprove) that all 9 node graphs are $2$-interval-PCGs, it
does not seem possible to apply our approach, even resorting to a most
efficient ILP model, as the ones described in [2, 3].

## Funding

This work was partially supported by Sapienza University of Rome.

## References

  * [1] S. Ahmed, M. S. Rahman, Multi-interval pairwise compatibility graphs, Proc. Theory and Applications of Models of Computation (TAMC 2017) Lecture Notes in Computer Science, Springer International Publishing, 2017, pp. 71–84.
  * [2] N. A. Azam, A. Shurbevski, H. Nagamochi, A method for enumerating pairwise compatibility graphs with a given number of vertices, Discrete Applied Mathematics 303 (2021) 171–185.
  * [3] N. A. Azam, A. Shurbevski, H. Nagamochi, On the enumeration of minimal non-pairwise compatibility graphs, Journal of Combinatorial Optimization (Sep. 2021).
  * [4] T. Calamoneri, A. Frangioni, B. Sinaimeri, Pairwise compatibility graphs of caterpillars, The Computer Journal 57 (11) (2013) 1616–1623.
  * [5] T. Calamoneri, D. Frascaria, B. Sinaimeri, All graphs with at most seven vertices are pairwise compatibility graphs, The Computer Journal 56 (7) (2012) 882–886.
  * [6] T. Calamoneri, E. Montefusco, R. Petreschi, B. Sinaimeri, Exploring pairwise compatibility graphs, Theor. Comput. Sci. 468 (2013) 23–36.
  * [7] T. Calamoneri, M. Lafond, A. Monti, B. Sinaimeri, On generalizations of pairwise compatibility graphs, manuscript (2022).
  * [8] T. Calamoneri, B. Sinaimeri, Pairwise compatibility graphs: A survey, SIAM Review 58 (3) (2016) 445–460.
  * [9] S. Durocher, D. Mondal, M. S. Rahman, On graphs that are not PCGs, Theoretical Computer Science 571 (2015) 78–-87.
  * [10] P. Kearney, J. I. Munro, D. Phillips, Efficient generation of uniform samples from phylogenetic trees, Proc. Workshop on Algorithms in Bioinformatics (WABI 2003) Lecture Notes in Computer Science, Springer Berlin Heidel-berg, 2003, pp. 177–189.
  * [11] S. Mehnaz, M. S. Rahman, Pairwise compatibility graphs revisited, Proc. International Conference on Informatics, Electronics and Vision (ICIEV 2013), IEEE, 2013.
  * [12] D. Phillips, Uniform sampling from phylogenetic trees, Master’s thesis, University of Waterloo, Canada (2002).
  * [13] M. S. Rahman, S. Ahmed, A survey on pairwise compatibility graphs, AKCE International Journal of Graphs and Combinatorics 17 (3) (2020) 788–795.
  * [14] M. N. Yanhaona, M. S. Bayzid, M. S. Rahman, Discovering pairwise compatibility graphs, Proc. International Computing and Combinatorics Conference (COCOON 2010), Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2010, pp. 399–408.


# Network Function Capacity Reconnaissance by Remote Adversaries

Paper #164

###### Abstract

There is anecdotal evidence that attackers use reconnaissance to learn the
capacity of their victims before DDoS attacks to maximize their impact. The
first step to mitigate capacity reconnaissance attacks is to understand their
feasibility. However, the feasibility of capacity reconnaissance in network
functions (NFs) (e.g., firewalls, NATs) is unknown. To this end, we formulate
the problem of network function capacity reconnaissance (NFCR) and explore the
feasibility of inferring the processing capacity of an NF while avoiding
detection. We identify key factors that make NFCR challenging and analyze how
these factors affect accuracy (measured as a divergence from ground truth) and
stealthiness (measured in packets sent). We propose a flexible tool, NFTY,
that performs NFCR and we evaluate two practical NFTY configurations to
showcase the stealthiness vs. accuracy tradeoffs. We evaluate these strategies
in controlled, Internet and/or cloud settings with commercial NFs. NFTY can
accurately estimate the capacity of different NF deployments within 10% error
in the controlled experiments and the Internet, and within 7% error for a
commercial NF deployed in the cloud (AWS). Moreover, NFTY outperforms link-
bandwidth estimation baselines by up to 30x.

##  1 Introduction

Attackers seek to optimize their impact by using reconnaissance probes to
assess a target’s resources before launching an attack. For example, prior
work has shown attackers can use topology information to launch sophisticated
denial-of-service (DoS) attacks and concentrate their efforts on important
nodes or links of a targeted network [panjwani2005experimental,
kang2013crossfire]. Particularly in attacks against critical network
infrastructures, a significant aspect of reconnaissance involves estimating
the capacity of network functions (NFs), which implement crucial operations,
including DDoS mitigation, firewall management, and network translation.
Anecdotal evidence suggests that attackers might be conducting such
reconnaissance to estimate the capacity of NFs before initiating DDoS attacks
(e.g., [schneier_2016, verisign_blog_2016, corero]). Accurately gauging the
capacity of various network function enables an adversary to identify the most
vulnerable targets and estimate the necessary resources (e.g., number of
packets, attack rate) for a successful attack.

Despite the potential risks and impact of such attacks, little is known about
the feasibility of Network Function Capacity Reconnaissance (NFCR). This paper
aims to raise awareness of NFCR attacks and guide potential targets towards
practical countermeasures. To the best of our knowledge, we are the first to
comprehensively define the problem of NFCR. Specifically, we are interested in
answering: _Can an attacker infer the processing capacity of an NF remotely
while remaining undetected (_e.g.,_ without sending too many packets)?_

At first glance, it seems an attacker can leverage the significant prior work
on link capacity estimation [jain2002end, lai2001nettimer,
carter1996measuring, kapoor2004capprobe] for NFCR. Yet, we find that link-
capacity estimation techniques are ineffective in the NFCR context due to
several unique challenges. First, unlike link-capacity estimation techniques,
which often involve sending large volumes of traffic[tirumala1999iperf,
mathis1996diagnosing], the number of packets sent for NFCR is crucial for its
success. Intuitively, sending more traffic increases the likelihood of the
target detecting the impending attack and bolstering capacity. Second, most
link capacity estimation techniques [saroiu2002sprobe, carter1996measuring]
require control over two vantage points before and after the link of interest,
which is not always easy to achieve, as NFs can be deployed within private
networks. Third, NFCR is affected by optimizations in the NF deployment such
as multi-threading and CPU frequency scaling, which are not typical to network
links whose capacity is stable, hence the bandwidth estimation techniques
[bolot1993characterizing, carter1996measuring, dovrolis2001packet,
jain2002end, kapoor2004capprobe, lai1999measuring, paxson1997end] are mostly
ineffective in NFCR.

Despite the challenges, we demonstrate the feasibility of NFCR by designing
and implementing a functional attacker strategy, which we call NF capaciTY
estimation (NFTY) that would allow an attacker to remotely and accurately
estimate an NF’s capacity while sending a relatively small number of packets
to evade detection. At a high level, NFTY operates by sending a burst of
packets designed to momentarily stress the NF, revealing its true capacity
despite hardware and software optimizations (not relevant in link capacity
estimation). NFTY measures the dispersion of the packets in the burst —a
concept borrowed from link-capacity estimation techniques— but innovatively
processes the dispersion measurements to reduce noise. NFTY is not only much
more accurate than link-capacity estimation baselines (up to 30x) but also
generalizes to an attacker controlling only a single vantage point by
leveraging the TTL-exceeded mechanism in Internet routers and surpassing other
associated practical issues (_e.g.,_ ICMP rate-limiting, router bottlenecks).

We design NFTY to be configurable depending on the attacker’s capability
(_e.g.,_ vantage points at sender and receiver), and her knowledge of the
target NF’s deployment (if any). Among all possible NFTY configurations, we
identify two concrete representative strategies and evaluate them in lab
settings and in the wild (public Internet, Internet2, cloud). The two attacks,
namely NFTY-100 and NFTY-5K, differ in the number of packets sent and thus
their effectiveness and visibility. At a high level, NFTY-100 is stealthier
but less accurate. Specifically, NFTY-100 works for an attacker that controls
two vantage points and sends only $100$ packets from one to the other.
NFTY-100 can accurately estimate the capacity of simple NFs with 9% in the
controlled environment and within 10% error in the Internet. We have used
NFTY-100 to estimate the capacity of a commercial NF in AWS within 7% of its
true capacity while avoiding detection.

NFTY-5K, in contrast, works even with an attacker controlling a single vantage
point and against more complex NFs but is less stealthy as it sends 5K
packets. We find that NFTY-5K estimates a more diverse set of NFs with up to
9% error in the controlled environment and within 9% error in the Internet.
This is up to 30x more accurately than the bandwidth estimation baselines.

We also propose practical countermeasures against NFCR attacks. Specifically,
we consider countermeasures that aim at adding noise to probing traffic or
obfuscating their infrastructure with rate-limiting and evaluating their
effectiveness and performance overhead.

Contributions:

  * $\bullet$

We are the first to formally define and analyze the feasibility of NF Capacity
Reconnaissance (NFCR).

  * $\bullet$

We investigate the applicability of bandwidth estimation techniques to NFCR
and identify the unique challenges that differentiate NF capacity estimation
from bandwidth estimation.

  * $\bullet$

We introduce NFTY, a flexible methodology for conducting NFCR, that is
accurate, stealthy, and practical even for an attacker that is single-sided
(_i.e.,_ cannot measure the packet it sends directly).

  * $\bullet$

We evaluate NFTY on both lab and Internet settings as well as against a
commercial NF in the cloud.

  * $\bullet$

We present a comprehensive suite of countermeasures designed to safeguard
potential targets against NFCR attacks with limited overhead.

##  2 Problem Formulation

In this section, we introduce the general problem of NF Capacity
Reconnaissance (NFCR) using a representative network setting. Next, we specify
the threat model and scope our problem.

Figure 1: The NF processes incoming traffic of the private enterprise. A two-
sided attacker controls nodes on both sides of the NF (in and out of the
enterprise), while a one-sided attacker controls nodes only outside the
enterprise (sender).

[Paper Setting]The NF processes the incoming traffic of the private
enterprise. A two-sided attacker controls nodes on both sides of the NF (in
and out of the enterprise), while a one-sided attacker controls nodes only
outside the enterprise.

Setting: We assume an enterprise that deploys a network function (NF) (e.g.
IPS, firewall) placed such that it observes all incoming traffic, as shown in
Figure 1. The NF comprises a set of processing tasks applied to a packet type
$t$ with a well-defined goal, such as load balancing or intrusion detection.
For example, a TCP SYN proxy NF is geared towards protecting against TCP SYN
flooding attacks. An NF can be deployed on different hardware (_e.g.,_ a
server, a programmable switch) with resources configured statically or
dynamically (_e.g.,_ number of threads, cores, memory). We define capacity
$\mathbb{C}_{p}$ of an NF as the maximum number of packets of type t ($p^{t}$)
the NF can process per unit time. An NF can have different capacities for
different packet types. Note that NFCR is not specific to a private enterprise
setting. It generalizes to other settings, such as the cloud, in which the NFs
are deployed by various third parties _e.g.,_ the Azure Marketplace [azure-
marketplace].

Threat Model: We consider two threat models depending on the attacker’s
capabilities as either _(i)_ one-sided or _(ii)_ two-sided; depicted in Figure
1. In the two-sided threat model, the attacker controls a vantage point (VP)
on both sides of the NF. The attacker can send traffic from one VP (e.g., a
host on the Internet) to the other (a host inside the enterprise network) via
the NF. In the one-sided threat model, the attacker controls a single VP
(e.g., a random Internet host). In both models, the attacker is unaware of the
deployment of the NF; the topology of the target network and location of the
NF; the congestion on the network path to the NF, and the NF itself. The
attacker aims to have a low network footprint to avoid detection. Beyond
preventing being blocked, the attacker’s low footprint prevents the victim
from noticing the reconnaissance and ramping up resources in preparation for
the real attack. Intuitively, the more packets an attacker sends, the more
visible and hence detectable they will be.

Problem Definition and Scope: Given this context, we formally define the NFCR
problem as follows: Given an NF with unknown processing capacity
$\mathbb{C}_{p}$ for packet type $p^{t}$, unknown location, and deployment,
construct an inference model that can remotely and accurately estimate the
capacity $\mathbb{C}_{p}$ for packet $p^{t}$ by probing it with at most budget
$\mathbb{B}$ packets.

In this paper, we restrict our focus to NFs whose processing capacity does not
depend on the packet history. The NF may maintain state, but that does not
affect its processing capacity, _i.e.,_ an attacker cannot decrease the
processing capacity of the target NF by sending certain packet sequences.
111Most Internet-facing NFs have this property to prevent an attacker from
algorithmic attacks exploiting this dependency to deplete the NF’s resources.
We also only consider statically provisioned NFs, meaning that their allotted
resources (cores, memory, hardware) do not change with time. Observe that the
NFs’ deployment can still use multi-threading or CPU optimizations but are
statically provisioned. This is common in practice, especially for
small/medium enterprises, as dynamically provisioning an NF is complex.222
Automating the entire lifecycle of NFs, from provisioning to decommissioning,
while handling workload fluctuations, real-time performance monitoring, and
decision-making makes dynamic provisioning a highly complex and nuanced task.
We consider an attacker that knows the high-level packet types that the target
NF processes (_e.g.,_ TCP SYN, UDP). The measured capacity will correspond
only to this packet type. This is not a limitation given that the attacker can
typically use packet types that correspond to commonly seen traffic, e.g., TCP
SYN, HTTP, DNS, and observe whether the output changes to identify which are
processed. Finally, similarly to bandwidth-estimation techniques
[bai1997estimating, bolot1993characterizing, clink, dovrolis2001packet,
jacobson1997pathchar, jain2002end, johnsson2004diettopp] which assume that the
target link is the bottleneck, NFCR assumes that the NF is the bottleneck in
the path (_i.e.,_ its processing rate is lower than that of the links).

##  3 Prior work and limitations

A natural starting point for an attacker is to use link-bandwidth estimation
techniques for NFCR. Hence, in this section, we try such techniques against
real NFs and show that they do not provide an accurate capacity estimate.
Finally, we reveal the unique characteristics of NFCR that make traditional
link-bandwidth estimation techniques ineffective.

###  3.1 Overview of Bandwidth Estimation

Based on the probing technique and the signal used, bandwidth estimation
techniques can be categorized into:

Dispersion-based techniques typically send a sequence or pair of packets and
measure the link-induced spacing at the receiver [carter1996measuring,
jacobson1997pathchar, li2008wbest, dovrolis2004packet]. Rate-based techniques
iteratively probe at varying rates until they find the minimum rate that
causes the one-way delay of packets to increase, signaling self-induced
congestion [ribeiro2003pathchirp, jain2002end]. Bulk-transfer techniques send
a high traffic volume for a longer duration and measure throughput (_i.e.,_
after self-induced drops) at the receiver [tirumala1999iperf,
allman2001measuring]. Using bulk transfer, an attacker might try to flood the
NF by sending packets at a high rate until drops are observed.

###  3.2 An Experimental Insight

We start by using each of these techniques to measure the capacity of
realistic NFs built on top of Snort [SnortNetworkIntrusion] and Suricata
[Suricata] and illustrate the results in Figure 2. We observe a huge
discrepancy among the three approaches. Naturally, the bulk transfer is the
most accurate. By offering excessive load, the NF runs at maximum capacity;
thus, the measured throughput is the capacity. While bulk transfer can serve
as an experimental ground truth, it does not satisfy NFCR. As bulk transfer
requires sending excessive traffic for an extended period to induce drops, it
will be extremely noticeable. Unfortunately, the less noticeable dispersion-
based and rate-based techniques (orange and blue bars) are extremely
inaccurate, with up to 65% and 54% error, respectively.

Figure 2: Traditional bandwidth-estimation techniques underestimate the
processing capacity of NFs. [Traditional bandwidth estimation
techniques]Traditional bandwidth-estimation techniques underestimate the
processing capacity of NFs.

###  3.3 Challenges of NFCR

We describe the characteristics that make NFCR challenging and traditional
bandwidth estimation techniques ineffective.

Optimized NF Deployments make NF capacity dynamic. Although we have scoped the
problem to statically provisioned NF (in §2), software and hardware
optimizations (_e.g.,_ CPU multi-threading or frequency scaling) still
introduce a level of variability in an NF’s effective capacity, which can
change based on current load conditions or the types of packets being
processed. This variability presents a significant challenge for Network
Function Capacity Reconnaissance (NFCR) techniques, which might underestimate
the NF’s capacity. In the context of bandwidth estimation, such variability
does not arise as there is no optimization affecting link capacity. In the NF
context, though, multi-threading –often used to increase the CPU efficiency–
can change the measured aggregate processing capacity of an NF. Similarly,
Dynamic Voltage and Frequency Scaling (DVFS) – used to adjust CPU frequency
based on load to reduce power consumption– can cause the attacker to
underestimate the capacity. Finally, unlike links for which same-length
packets are processed at a similar speed, NF’s speed might be affected by the
packet type or flow distribution, _e.g.,_ due to thread scheduling, hence
there is need for more diverse probes.

Two-sided estimation techniques do not generalize to one-sided. Traditional
bandwidth-estimation techniques typically assume two-sided control of the
link. This is natural as those techniques were designed as a benign tool for
operators controling their network. In this paper, we aim to investigate the
effectiveness of an attacker performing NFCR that might only have one-sided
control. Link bandwidth estimation techniques that work under the one-sided
assumption typically rely on a particular protocol behavior involving specific
packet types (_e.g.,_ a TCP SYN on a closed port triggers a TCP RST
[saroiu2002sprobe]) and thus do not generalize to any $p^{t}$ that the target
NF is processing.

Measurement infrastructure introduces noise. Intuitively, the used
infrastructure is crucial for any measurement campaign. In the context of
NFCR, accuracy in sending packets at a concrete rate and monitoring packets’
arrival timestamps is crucial and surprisingly hard to achieve in practice.
Intuitively, optimization at the receiver, _e.g.,_ batching in software (NAPI
[salim2001beyond]) or hardware (IC [IC]), result in very coarse-grained packet
timestamps, which might undermine the measurements. Similarly, software-based
packet generation is easier to implement but is unlikely to offer reliable
rates for probing. While these are concerns shared with bandwidth-estimation,
we report our unique insights in §LABEL:sec:measurements.

##  4 NFTY overview

In this section, we give an overview of NFTY and describe its most critical
design decisions via intuitive examples. Consider an attacker that aims to
estimate the maximum packet processing rate of an NF for a particular packet
type (e.g. UDP). The NF is deployed at the edge of a victim network (as in
Fig. 1). The attacker might control the sender only (one-sided threat model)
or both sender and receiver (two-sided threat model). To this end, the
attacker sends a set of UDP packets to a host such that they are processed by
the NF. To remain stealthy, the attacker does not flood the NF or use rate-
based iterative probing. Instead, the attacker measures the dispersion _i.e.,_
the NF-induced time gap between consecutive packets to infer the NF processing
capacity. After being processed by the NF the packets will be spaced out in
time depending on the NF processing time (Figure 3). The attacker manages to
cause the NF to run at its maximum (true) rate, while staying under the
radar.The burst instantaneously stresses the NF and creates a clear step-wise
pattern in the dispersion values that the attacker can recognize and use to
find the true capacity. We elaborate on how the attacker adapts traditional
dispersion-based techniques to the NFCR context in §5.1.

If the attacker is two-sided _i.e.,_ controls a receiver, the attacker
measures the packet dispersion directly ( Fig.3). If the attacker is one-
sided, she engineers a subset of the sent packets to trigger an error message
from an on-path router after the NF. Next the one-sided attacker measures the
dispersion between consecutively received error messages (§5.3). As an
illustration, Fig. 5 shows an one-sided attacker that triggers the router to
send a TTL time exceeded error message (after processing by the NF) back to
the sender. Notably, NFTY does not need to receive trigger engineer all
packets to return as error messages.

NFTY generalizes to multiple NFs and deployments and is configured with two
parameters: _(i)_ the number of packets it sends; and _(ii)_ (for one-sided
only) the gap between packets that trigger a router in the path. Intuitively,
sending more packets allows for higher accuracy as it triggers the NF’s true
behavior, but makes the attack more detectable. We analytically and
experimentally find the minimum number of packets that need to be sent to
accurately estimate an NF’s capacity. We discuss our findings in
(§LABEL:sec:e2e) and summarize our results in a decision tree in
Fig.LABEL:fig:decision-tree.

##  5 Design

In this section, we explain how we adapted the dispersion-based estimation to
the NFCR context. We first show analytically the connection between dispersion
and NF capacity. Next, we explain how NFTY process dispersion measurements to
estimate the true NF capacity; how NFTY generalizes to one-sided and how it
can be parameterized using the probe length.

###  5.1 Dispersion-based Strategy to NFCR

Figure 3: In the two-sided threat model, the time difference between
consecutive packets increases as packets exit from the NF revealing NF’s
processing time, thus its capacity.

In this subsection, we explain how we can adapt dispersion-based bandwidth
estimation approaches for NFCR. Dispersion-based techniques seek to estimate
the bandwidth of a bottleneck link by sending a probe of two (i.e., a pair) or
more (i.e., a train) packets back to back and measuring their spacing at the
receiver. To see the intuition, consider the case of a packet pair. Assuming
that the link capacity of the bottleneck link is lower than the packets’
inter-arrival rate, the second packet of a packet pair will be queued, waiting
for the transmission of the first one. The time difference between the arrival
of the two packers in their destination is called dispersion $\delta$ and
gives the transmission time $t_{tr}$ on the bottleneck link. We can then
calculate the bottleneck link capacity $C_{l}$ for a packet of size $S$ as
follows: $C_{l}=S/t_{tr}=S/\delta$.

This basic idea assumes that processing delays on path are negligible compared
to link transmission delays. Yet, if the pair traverses an NF the measured
dispersion depends on the NF’s processing $t_{p}$ time, which is typically
higher than transmission time since it does more than forwarding. Hence, to
adopt dispersion based bandwidth estimation for NFCR where the packet also
traverses an NF, the dispersion is:

$\displaystyle\delta=\max(t_{tr},t_{p})=\max(S/C_{l},1/\mathbb{C}_{p})$ (1)

Thus, if we assume that the NF’s processing time $t_{p}$ is larger than the
transmission time $t_{tr}$ then measured dispersion corresponds to the former.
As an illustration, in Fig. 3 the sender forwards back-to-back packets, they
will be queued at the NF. For each $p_{i}$, the next packet $p_{i+1}$ will
only be processed after the NF is done processing $p_{i}$ (as the NF is
single-threaded). In other words, packets are dispersed by the time it takes
to process a packet at the NF. Hence, the amount of dispersion between packets
$\delta$ at the receiver gives the processing time $t_{p}$ of the NF. From
this dispersion $\delta$ between packets, the processing capacity
$\mathbb{C}_{p}$ of the NF can be estimated as we discuss next.

###  5.2 Estimation Approach for NFCR

Unlike link bandwidth estimation, estimating the processing capacity of an NF
using dispersion requires considering additional factors. As we hint in §3.2,
these factors include: _(i)_ DVFS at NF; _(ii)_ multi-threading at NF; _(iii)_
batching at receiver. After defining the problem, we elaborate on how each of
these factors affects the dispersion values we measure. Next, we explain why
applying seemingly natural calculations to the measured dispersion values
would not yield a correct capacity estimation. Finally, we describe how we
analyze dispersion measurements to estimate capacity.

Problem: After sending a packet train of $L$ packets, we measure the
dispersion of the received packets. For every train of size $L$, we calculate
$L-1$ dispersion values ($D=\delta_{1}..\delta_{L-1}$). To estimate We want to
compute a dispersion value that corresponds to the time when the NF was
operating at its maximum capacity. We call this dispersion value as the
desired dispersion $\delta^{*}$ which is a function $F$ of all the measured
dispersion values $D$.

Challenge 1: Because of DVFS, not all dispersion values correspond to the true
capacity. Consider an NF that runs on a CPU configured with DVFS. The CPU will
operate at a lower frequency under lighter load, transitioning to a higher
frequency under heavier load driven by the OS or kernel. In the context of
NFCR, DVFS can cause the observed rate at which packets are processed to
change as a CPU might undergo multiple transitions in frequency before
reaching its maximum frequency. As a result, the measured dispersion values do
not all correspond to the true capacity. For example, Fig. 4(a) shows the
dispersion values that will actually be observed if DVFS is enabled at the NF.
The dispersion values go through multiple transitions.

Challenge 2: Multi-threading and batching of packets introduce spikes in
dispersion values. As a result of multi-threading at NF or batching at
receiver, there can be spikes in the dispersion graph as shown in Figure 4(b).

(a)

(b)

Figure 4: (a) Assuming that the last step corresponds to maximum frequency is
incorrect due to the potential under-clocking. (b) Batching can cause spikes
in the dispersion signature. Hence, choosing a probe length larger than the
batch interval is important.

Strawman solutions: A straightforward approach for $F$ would be to choose the
minimum dispersion value. In this case
$F(D)=min(\delta_{1},\delta_{2},...,\delta_{L})$ and the capacity
$\mathbb{C}_{p}$ is given by
$\mathbb{C}_{p}=1/\min(\delta_{1},\delta_{2},...,\delta_{L})$. Unfortunately,
this natural estimate could lead to inaccurate results. The minimum dispersion
could represent a moment of (self-induced) congestion which would cause two
packets to wait into the same queue effectively modifying their dispersion.
Moreover, presence of batching and multi-threading will also distort this
value.

An alternative approach is to calculate the mean or median dispersion value
across the last $N$ packets in the train, since these packets are more likely
to have observed the maximum frequency, if the train itself has triggered it.
In this case, $F(D)=mean(\delta_{L-N},\delta_{L-N+1},...,\delta_{L})$ and
$\mathbb{C}_{p}$ will be
$\mathbb{C}_{p}=1/mean(\delta_{L-N},\delta_{L-N+1},...,\delta_{L})$.

Finally, one could chose the configuration of $N$ by finding the last step in
the dispersion values using a step detection algorithm. This approach
implicitly assumes that CPU frequency transitions from low to high and then
remains there until the load subsides. However, we observed that in certain
cases, frequency may transition back to a low frequency as shown in Fig. 4(a).

NFTY uses step detection to find the dispersion values corresponding to the
maximum frequency. To avoid the shortcomings of previous methods, NFTY first
performs step detection [truong2020selective] on the sequence of dispersion
values $D=\delta_{1},\delta_{2},...,\delta_{L}$. Second, it divides D in to a
set of segments $S$ at the detected steps. Third, for each segment
$\delta_{i\rightarrow{j}}\in S$ from $\delta_{i}$ to $\delta_{j}$, it computes
the mean dispersion value of the segment. We choose mean dispersion because it
generalizes to the case of batching and multi-threading. After that, NFTY
picks the minimum mean dispersion values as $\delta^{*}$. Given segments
$\delta_{i\rightarrow j}\in S$, we calculate $\delta^{*}$ as:

$\displaystyle\delta^{*}=\min_{\delta_{i\rightarrow j}\in
S}\dfrac{\sum_{n=i}^{j}(\delta_{n})}{j-i+1}$ (2)

For step-detection, we consider algorithms which do not require number of
steps as input becuase the NF may transition to many steps which will vary
across deployments. Hence, we consider a different class of step detection
algorithms [truong2020selective] which use penalty functions to separate noise
from steps. Among these algorithms, we choose Binary Segmentation
[bai1997estimating] as it is widely used [chen2012parametric,
fryzlewicz2014wild]. We use the Gaussian Kernel [garreau2018consistent] as our
cost function to measure variations in the data as it empirically works well.
We use linear penalty [truong2020selective] for step detection based on
empirical observations.

###  5.3 NFTY with One-sided Control

NFTY, as we have described it so far, relies on the timestamped packets that
the receiver reports. In this subsection, we explain how NFTY can be extended
to the one-sided threat model.

While some prior works wave the requirement of a receiver that is controlled,
they are not applicable for NFCR. For instance, Saroiu et al.
[saroiu2002sprobe] send TCP SYN requests aiming at triggering a TCP RST. An
alternative approach from Carter et al. [carter1996measuring] sends an ICMP
ECHO REQUEST aiming at triggering a ICMP REPLY. In both cases, the solution
relies on the use of particular packet types which trigger protocol-specific
behavior, that might not trigger any processing from the NF.

NFTY exploits the error messages, namely _ICMP time exceeded_ sent as error
messages from routers to hosts upon receiving an IP packet that has no time to
reach its destination. Concretely, each IP packet carries a Time To Live (TTL)
value in its header. As routers in the Internet path forward an IP packet,
they decrement this value by one. If the TTL reaches zero (expires) before the
packet reaches its destination, an _ICMP time exceeded_ message is sent by the
last router that decremented it to the sender. To trigger this behavior, the
attacker: _(i)_ sends packets towards a destination IP that is within the IP
address space allocated to the targeted network;333IP address space allocation
is public information. and _(ii)_ sets the TTL of the probing packets such
that the TTL expires after the packet is processed by the NF but before the
packet reaches its destination. The attacker can discover the appropriate TTL
by using traceroute [TracerouteLinuxMan].444For example, the attacker can
target the last router in the path that replies to traceroute. Traceroute is a
standard measurement tool that relies on the TTL expiration mechanism and
allows the sender to observe the path (the series of routers) that a packet
takes to a destination. Importantly, TTL is part of a standard IP header and
hence it generalizes to various packet types.

Figure 5: One-sided threat model: While a router can be used to echo the
packets back to the receiver (triggering ICMP TTL time exceeded), its
processing rate may change the spacing across packets (dispersion),
effectively ruining the signature.

While promising, relying on _ICMP time exceeded_ to calculate NF dispersion is
challenging. In fact, the use of ICMP replies has known limitations which are
well studied in the context of traceroute [detal2013revealing,
gunes2008resolving]. We focus on three factors that are particularly impactful
in our context, as they obfuscate the dispersion signals. These are related to
the router processing time, contention at the router or potential rate-
limiting of ICMP traffic:

  * 1.

The router processing time might overwrite the NF dispersion. In this case,
the observed dispersion would correspond to the router’s processing time
_i.e.,_ not the NF’s processing time. We illustrate this issue in Figure 5.
This is not a problem in the case of two-sided in which routers only forward
the probing packets (instead of dropping them and generating a new packet).

  * 2.

The router in which the TTL expires might be congested with regular traffic,
thus adding random delays to ICMP replies. In such cases, routers prioritize
regular packet forwarding from control tasks which are often best effort. The
random delays added to the ICMP packets will make their dispersion useless for
the attacker.

  * 3.

ICMP ratelimiting may cause the routers to not respond at all. Finally, an
operator might rate-limit the ICMP traffic [ICMPRatelimiting] for performance
or security reasons. For example, in our experiments, we tried three routers
in the university network and found that two of them rate-limited packets at
five packets per second as also observed by Ravaioli  _et al._
[ravaioli2015characterizing] who foun that 60% of the routers in the Internet
implemented ICMP TTL Exceeded rate limiting.

NFTY configures only a subset of the probing packets that are spaced in time
to trigger ICMP replies.

To effectively addresse the aforementioned limitations, we use two insights
NFTY configures only a subset of the probing packets that are strategically
spaced in time to trigger an ICMP TTL Time Exceeded error from a router. This
alleviates the effect of ICMP rate-limiting and the processing time of the
router.

First, while NFTY needs to send large trains to trigger frequency scaling,
NFTY only needs the dispersion from a small number of packets to estimate
$\mathbb{C}_{p}$. Second, to measure dispersion, NFTY does not need the
arrival times of consecutive packets, instead NFTY can calculate the mean
dispersion $\bar{\delta}$ between two packets $p_{i}$ and $p_{j}$, which
arrive at the receiver at $t_{i}$ and $t_{j}$ by $\delta=(t_{j}-t_{i})/(j-i)$

Next, we explain how we use these insights to mitigate the effects of rate-
limiting, router processing times, and router load. Consider that the attacker
sends a packet train of length $L$ at time $\tau^{send}$. The attacker sets
the TTL of packet $p_{i}$ and some other non-consecutive packet $p_{j}$ to
expire at some router $r$. The packets arrive at the NF, which takes time
$t_{p}$ to process each packet. The first packet $p_{1}$ sees no queuing delay
at the NF. The second packet is queued for time $t_{p}$ and packet $p_{i}$ is
queued for time $(i-1)t_{p}$ because $i-1$ packets will be processed before
the packet $p_{i}$. Then, the packet $p_{i}$ arrives at the router, which will
see that $p_{i}$ has expired TTL, and it will generate an ICMP TTL time
exceeded with processing delay $t_{r}$. Then, let $\tau^{r}_{i}$ be the time
the reply for packet $p_{i}$ arrives at the sender, and $\tau^{r}_{j}$ be the
time the reply for packet $p_{j}$ arrives at the sender.

If $d_{i}$ is the total delay when packet $p_{i}$ left the sender and its ICMP
Reply arrived at the sender, then $\tau^{r}_{i}$ is:

$\displaystyle\tau^{r}_{i}=$ $\displaystyle\tau^{send}+d_{i}$ (3)
$\displaystyle\text{where }d_{i}=$ $\displaystyle t_{p}+t_{r}+(i-1)t_{p}+c$

$c$ is for the constant transmission and propagation delay; $t_{p}$ is the
processing delay experienced by the packet $p_{i}$ at the NF; $t_{r}$ is the
router processing delay in generating an ICMP reply; $(i-1)t_{p}$ is the
queuing delay experienced by the packet. We choose packet $p_{j}$ such that
when it arrives at the router, packet $p_{i}$ has already been processed. This
ensures that packet $p_{j}$ does not see any queuing at the router. Then for
packet $p_{j}$, $\tau^{r}_{j}$ is given by:

$\displaystyle\tau^{r}_{j}=$ $\displaystyle\tau^{send}+d_{j}$ (4)
$\displaystyle\text{where }d_{j}=$ $\displaystyle t_{p}+t_{r}+(j-1)t_{p}+c$

At the sender, we can calculate the dispersion as follows:

$\displaystyle\delta=\tau^{r}_{j}-\tau^{r}_{i}$ (5)

Substituting Equation 3 and Equation 4 in 5, we get:

$\displaystyle\delta=$ $\displaystyle\tau^{send}+t_{p}+t_{r}+(j-1)t_{p}+c$
$\displaystyle-\tau^{send}-t_{p}-t_{r}-(i-1)t_{p}-c$ $\displaystyle\delta=$
$\displaystyle(j-i)t_{p}$ (6)

From Equation 6, the processing capacity $\mathbb{C}_{p}$ can be estimated as
follows:

$\displaystyle\mathbb{C}_{p}=1/t_{p}=(j-i)/\delta$ (7)

Having explained why we do not need to trigger an ICMP error in every packet
of our probe, the next natural question is how to choose these packets. To
decide that, we need to look at our constraints. We want to space the packets
such that when packet $p_{j}$ arrives at the router, packet $p_{i}$ has
already been processed. This requires an estimation of an _upper-bound_ of
router processing time. We can estimate processing time by sending packet
pairs with the correct TTL. The spacing of the replies will give the router
processing time. For example, in our experiments, we found that the router
took 55us to process and generate ICMP replies.

Once we have an estimation of the router processing time, we can choose the
packets such that when they arrive at the router, they are at least $t_{r}$
apart. For example, for a router processing time of 100us, we can set the TTL
after every 100 packets, assuming our send rate is 1Mpps. Concretely, for a
router processing time of $t_{r}$, and the maximum capacity $C_{max}$ that the
attacker can send, we can set the TTL after a gap of $g_{TTL}$ packets where
$g_{TTL}$ is chosen such that $g_{TTL}>t_{r}\times C_{max}$, $t_{r}\times
C_{max}$ gives the num,ber of packets that arrive at the router in time
$t_{r}$. Observe that the NF processes packets before they arrive at the
router. Thus, the actual duration between the packets will be much greater
than $t_{r}$. For example, consider that we have an NF, which processes each
packet in 5us, and a router takes 100us to generate an ICMP reply. If the
sender sets the TTL of every 100th packet, then if the first packet arrives at
the router at time t, the 101st packet will arrive at
$((5us)+(100)(5us))\times t$, which is much greater than 100us. Importantly,
the estimation of the processing in the router need not be extremely accurate.
In fact, we only need to make sure that the packets are spaced out more than
the processing time.

##  6 Evaluation

We evaluate the accuracy and the stealthiness of NFTY in two representative
configurations, namely NFTY-5K and NFTY-100, which send 5K and 100 packets,
respectively in controlled and Internet experiments. We find that NFTY-5K is
up to 30x more accurately than a baseline sending the same number of packets
per probe. NFTY-100 is accurate only on a subset of the NF deployments but is
more stealthy. NFTY-100 is up to 20x more accurate in controlled experiments
compared to the equivalent baselines sending the same number of packets.
Importantly, we find that NFTY-100 can accurately estimate the capacity of a
commercial NF in AWS within 7% of error. We also evaluate the impact of each
individual optimization in NFTY and find that step-detection and an optimized
measurement infrastructure are crucial to NFTY’s accuracy.

Figure 6:  Our Internet setup forwards packets through the Internet after they
have been processed by the NF. This is the worst-case scenario for the
attacker (and NFTY) as the Internet noise can affect the dispersion. In the
one-sided experiments, we send probes to the Clemson node but they expire on
path, causing ICMP replies to the sender(shown in dotted).

[Internet Setup]Our Internet setup forwards packets through the Internet after
they have been processed by the NF. This is the worst-case scenario for the
attacker (and NFTY) as the Internet noise can affect the dispersion signature
of NF. In the one-sided experiments, we send probes to the Clemson node but
they expire on path, causing ICMP replies to the sender(shown in dotted).

###  6.1 Methodology

Probing baseline: We evaluate our approach against a rate-based bandwidth-
estimation technique, namely SLoPS in which the attacker uses binary search
for NFCR [jain2002end] between 0-500Kpps. The attacker sends packets to the NF
at an initial probing rate (250Kpps) and uses one-way delay of received
packets to see if the probe rate (pps) caused congestion indicating that the
rate was greater than the NF capacity. If so, it adjusts the probe rate
accordingly using a binary search approach. SLoPS keep probing until the
difference between minimum and maximum rate is 1000pps. To find an increasing
trend in the relative one-way delay values, we use the technique implemented
by Pathload [jain2002end]. Moreover, we use the same probe length for the
baseline and for NFTY.

Estimation baselines: To evaluate the estimation technique used by NFTY, we
compare with two baseline approaches adopted from the link bandwidth
estimation literature _(i)_ mean-train which takes the mean dispersion of the
entire train [dovrolis2001packet]; and _(ii)_ median-train which takes the
median dispersion [li2008wbest].

Network functions: We use five NFs. Both SNORT-RL and SUR-RL are realistic TCP
SYN rate-limiting NFs which we implemented in Suricata [Suricata] and Snort
[SnortNetworkIntrusion] respectively. Both NFs track the number of SYN packets
per flow and drop the SYNs of flow that have exceeded a threshold. For SNORT-
RL and SUR-RL, we send SYN packets. SUR-BL is a deny list containing rules
provided by the emerging threats database [ProofpointEmergingThreats]. We only
send UDP traffic to SUR-BL to trigger the rules concerning UDP traffic. We
implemented SUR-BL in Suricata [Suricata]. SUR-BL-mt and SUR-RL-mt are multi-
threaded versions of SUR-BL and SUR-RL respectively.

NF ($\mu s$) | Controlled | Internet | One-sided
---|---|---|---
SNORT-RL | 67500 | 21000 | 21800
SUR-BL | 142600 | 134640 | 143420
SUR-RL | 200880 | 193750 | 225140
SUR-BL-mt | 227720 | 224680 | 216000
SUR-RL-mt | 336060 | 360460 | 309140
TABLE I: The ground-truth processing capacity of our NFs measured in packets
per second (pps) for our experimental setups. Processing capacity varies for
different NFs and across deployments (_e.g.,_ processors, NIC, configuration)

(a)

(b)

(c)

Figure 7: (a) NFTY-5K is up to 30x more accurate than the baseline in
optimized NF deployments for the same probes length. (b) By applying step
detection to the dispersion values, the MdAPE of NFTY-5K is reduced by up to
25x.  (maria: add to label step-detection?) (c) As we increase the probe
length, the accuracy of NFTY improves.

[NFTY-5K Performance](a) NFTY-5K is up to 30x more accurate than the baseline
in optimized NF deployments for the same probes length. (b) By applying step
detection to the dispersion values, the MdAPE of NFTY-5K is reduced by up to
25x.  (maria: add to label step-detection?) (c) As we increase the probe
length, the accuracy of NFTY improves.

Ground-truth measurements: To measure the ground-truth processing capacity for
our NFs, we send packets to a receiver node via each NF using Scapy
$\mathit{sendpfast}$ [rohith2018scapy]. We do a binary search on the sending
rate until we find the maximum rate that allows the input rate of the NF node,
to equal its output rate (_i.e.,_ the maximum sending rate without packet
drops at the NF). We repeat this exercise five times and choose the median as
the ground-truth. We show our results in Table I. We measure the ground-truth
capacity for each setup and NF separately, as it can be affected by hardware
and software factors (_e.g.,_ processor, NIC). We repeat each experiment 100
times and report the Median Absolute Percentage Error (MdAPE) in the estimated
processing capacity compared to the ground truth (Table I).

(a)

(b)

(c)

Figure 8: (a) NFTY-100 results in 3% to 9% error in the estimated processing
capacity with the optimized measurement infrastructure. SLoPS-100 results in
high error (up to 61%) for faster NFs as the sender cannot send packets faster
than the NF because of DVFS at sender. (b) When we use NFTY-100 in an
optimized measurement infrastructure, the MdAPE is reduced by up to 33x. The
improvement is significant for the larger batch interval (batch-300us) as
compared to the smaller interval (batch-100us). (c) NFTY-100’s error remains
below 10% in the internet. The spread is a bit higher than the controlled
experiments for very fast NFs due to the noise added by the Internet.

[NFTY-100 Performance](a) NFTY-100 results in 3% to 9% error in the estimated
processing capacity with the optimized measurement infrastructure. SLoPS-100
results in high error (up to 61%) for faster NFs as the sender cannot send
packets faster than the NF because of DVFS at sender. (b) When we use NFTY-100
in an optimized measurement infrastructure, the MdAPE is reduced by up to 33x.
The improvement is significant for the larger batch interval (batch-300us) as
compared to the smaller interval (batch-100us). (c) NFTY-100’s error remains
below 10% in the internet. The spread is a bit higher than the controlled
experiments for very fast NFs due to the noise added by the Internet.

###  6.2 Controlled experiments

We start by comparing NFTY-5K and NFTY-100 to baselines in a controlled lab
experiment of three nodes in CloudLab [duplyakin2019design], a sender, a
receiver, and an NF connected such that the sender communicates to the
receiver via the NF node. All Intel Haswell EP nodes with two 10-core CPUs
with 2.60 GHz frequency.

NFTY-5K outperforms probing baselines by 2x-30x while sending less packets in
total. Figure 7(a) shows the MdAPE in the estimated capacity by NFTY-5K and
SLoPS. NFTY-5K results in 2%-9% error for the five NFs and outperforms the
baseline. The improvement is more prominent in the faster NFs, compared to
SNORT-RL, which is slower (see Table I). The baseline also ends up sending 9x
more packets (median in NFs) than NFTY-5K, due to its iterative probing.
Still, the baseline’s poor accuracy is due to its obliviousness to the
fluctuation of one-way delays caused by the NF’s optimized deployment (_i.e.,_
frequency transitions). Moreover, for multi-threaded NFs (last two bars), the
baseline ends up triggering only a single thread because both the multi-
threaded NFs assign packets to threads on the basis of flow. Importantly, both
techniques use the optimized measurement infrastructure we describe in
§LABEL:sec:measurements. The baseline precision further degrades with an
unoptimized measurement infrastructure, as we show later (Figure 8(a)).

Step-detection improves NFTY-5K accuracy by up to 25x To investigate the
benefit of step detection, we compare NFTY-5K with the estimation baselines,
mean-train and median-train. We summarize our results in Figure 7(b). We
observe that the reduction in MdAPE is significant. For SNORT-RL the
improvement over the baseline is less compared to the other NFs because SNORT-
RL changes to maximum frequency sooner than the other NFs. In effect, mean-
train is closer to the one corresponding to the maximum frequency. median-
train precision degrades further for multi-threaded NFs, because of the
fluctuations in queueing delays for subsequent packets it causes.

Longer probe lengths are critical for NFs with DVFS. Figure 7(c) shows the
effect of different probe lengths on NFTY’s error in the presence of DVFS.
Longer trains for NFTY result in low errors (MdAPE) because they always
trigger the transition to the maximum frequency. In contrast, small trains
never trigger the transition to maximum frequency. Thus, if the attacker were
to perform NFCR with NFTY-100 in the presence of DVFS, she would have a high
error. The frequency transitions happen sooner for slow NFs as compared to the
faster ones. Note that all NFs show a transition at length of 500 packets.

NFTY-100 accurately estimates capacity within 9% of error. Since we have shown
that NFTY-100 cannot estimate the capacity of NFs whose deployments are
optimized with DVFS (Figure7(c)), we evaluate NFTY-100 for simpler NF
deployments. We find that NFTY-100 estimates the capacity of these with 2% to
9% error as shown in Figure 8(a). We compare NFTY-100 with SLoPS-100. For
NFTY-100, we turn DVFS off at sender, as with small number of packets, its
effect becomes significant. For the baseline, DVFS is not off at the sender.
We observe that the error and the spread for SLoPS-100 increase up to 61%.
Specifically, for SLoPS-100 the error is huge for NFs (SUR-RL to SUR-RL-mt)
where the attacker cannot send at rates higher than the NF processing speed.
This highlights the importance of our sender-side optimizations. Hence, if an
attacker were to use SLoPS-100 without our sender-side optimization, she would
incur a huge error.

NFTY’s measurement optimizations improve the accuracy of NFTY-100 by up to 33x
In the previous experiment, we already hinted that the most impactful factor
in NFTY-100 accuracy is the measurement infrastructure, as we discuss in
§LABEL:sec:measurements. To verify that we plot the overall improvements
caused by our measurement optimizations in Figure 8(b) . For the unoptimized
measurement infrastructure, DVFS is enabled at the sender, and we show two
receiver configurations, one with a batch interval of 100us and the other with
a batch interval of 300us. For the optimized measurement infrastructure, DVFS
is disabled at the sender, and there is no packet batching. As shown in Figure
8(b), our measurement-infrastructure optimizations in NFTY-100, reduce its
MdAPE by upto 33x.

NFTY is less detectable than SLoPS while being more accurate To evaluate the
detectability of NFTY, we use the ruleset of known commercial firewalls Palo
Alto Networks (PANW) , Juniper , Fortinet , and Snort community rules . We
implement these rulesets in Suricata, and record if these rulesets detect NFTY
and SLoPS. Table II summarizes our results for TCP SYN traffic processed by
SUR-RL, SUR-RL-mt, and SNORT-RL and UDP traffic processed by SUR-BL, and SUR-
BL-mt. A tick indicates that the firewall was able to detect the attack. A
cross indicates that the attack is not detected. Overall, NFTY is less
detectable than the baseline.

|  | PANW | Juniper | Fortinet | Snort
---|---|---|---|---|---
NFTY-5K | TCP SYN | ✗ | ✗ | ✓ | ✗
SLoPS-5K | ✓ | ✓ | ✓ | ✗
NFTY-100 | ✗ | ✗ | ✗ | ✗
SLoPS-100 | ✗ | ✗ | ✗ | ✗
NFTY-5K | UDP | ✗ | ✓ | ✓ | ✗
SLoPS-5K | ✓ | ✓ | ✓ | ✗
NFTY-100 | ✗ | ✗ | ✗ | ✗
SLoPS-100 | ✗ | ✓ | ✗ | ✗
✗$=$ not detected |  ✓$=$ detected |  |
TABLE II: NFTY is less detectable than SLoPS while being more accurate
(maria: What are the columns?)

###  6.3 Internet-2 and One-sided Experiments

So far we only evaluated NFTY in pristine network conditions. Having shown
that NFTY outperforms baselines by orders of magnitude, in this subsection we
aim to verify whether NFTY is usable in more realistic settings _e.g.,_ on the
Internet or in cases where the attacker only controls the sender (single-
sided) and thus relies on a router.

Internet setup: Our sender and the NF node run in CloudLab Wisconsin, and our
receiver node runs in Clemson. As we illustrate in Figure 6, the packets from
the NF to the receiver go through the Internet. We stress that this is the
worst-case scenario for the attacker. Indeed, if the packets in a probe see
congestion in the Internet before reaching the NF, the random delay/noise from
the Internet would not affect the NF-induced dispersion. We run this
experiment at different times of the day to capture the effect of varying
congestion in the Internet. The sender and the receiver use the same nodes as
in the controlled environment. The receiver uses Intel Haswell E5-2683 v3
nodes with 14-core CPUs and 2.00 GHz frequency.

Both NFTY-100 and NFTY-5K remain within 10% error in the Internet. We evaluate
NFTY-100 (without DVFS at the NF) in the Internet to show that NFTY can
accurately estimate the capacity even in the Internet using only a small
number of packets. We summarize our results in Figure 8(c). NFTY-100 can
accurately estimate NF’s capacity within 10% error. The spread in error values
for faster NFs is higher than in controlled experiments. We also evaluate
NFTY-5K (with DVFS at the NF) to show that even with added noise from the
Internet, shown in Figure 9(a) the NFTY-5K’s estimation using step detection
works well. NFTY-5K has a higher spread in MdAPE in the Internet compared to
the controlled environment. However, the MdAPE in the Internet for NFTY-5K
also remains within 9% error.

(a)

(b)

Figure 9: (a) NFTY-5K results in 4% to 9% MdAPE in the Internet with optimized
NF deployment (with DVFS). (b) NFTY results in 4%-10% MdAPE with one-sided
control. In both cases, the spread in error is a bit high for fast NFs
compared to SNORT-RL, _i.e.,_ the slowest NF.

[NFTY-5K Performance on Internet](a) NFTY-5K results in 4% to 9% MdAPE in the
Internet with optimized NF deployment (with DVFS). The spread in error
increases with faster NFs. (b) NFTY results in 4%-10% MdAPE with one-sided
control. Our spread is a bit high for fast NFs compared to SNORT-RL, _i.e.,_
the slowest NF.

One-sided setup: We illustrate the setup of this experiment in Figure 6. The
sender and the NF are in the Wisconsin cluster and they send packets to a
public server in the Clemson cluster. The TTL is set such that it expires in 4
hops after being processed by the NF. We choose $g_{TTL}$ (_i.e.,_ the gap in
packets for which we set the correct TTL) to be 100 packets.

NFTY-5K is usable under the one-sided threat model. We summarize our results
in Figure 9(b). For the experiments with one-sided threat model, NFTY-5K’s
MdAPE remains around 10%. Faster NFs such as SUR-RL-mt show a higher spread as
in the case of two-sided Internet experiments. This shows that indeed, NFTY
with one-sided control is feasible and can result in reasonable estimation of
the processing capacity of an NF.

(a)

(b)

Figure 10:  (a) In the AWS experiments, the sender probes the NF from the
Internet. (b) NFTY-100 results in 7% MdAPE while probing a commercial NF
Fortinet next generation firewall [fortinet]. The spread is high because here,
the receiver and the NF are VMs and may induce extra noise.

[AWS Experiments](a) In the AWS experiments, the sender probes the NF from the
Internet. (b) NFTY-100 results in 7% MdAPE while probing a commercial NF
Fortinet next generation firewall [fortinet]. The spread is high because here,
the receiver and the NF are VMs and may induce extra noise.

###  6.4 Internet Experiments

Now we evaluate NFTY outside of the Internet2 setting which had packets sent
only between Cloudlab machines. In these experiments, we provide an even more
realistic setting for an attacker operating in a two sided model where they
control both the sender and receiver.
Internet setup: Our sender and the NF run in Cloudlab Wisconsin, and our
receiver node runs in Vultr Los-Angeles. Similar to figure 6, as the packets
travel from the Cloudlab machines to the Vultr machine, they traverse the
Internet. Unlike in the Internet2 experiments, the packets are no longer
travelling through the isolated environment that the Cloudlab network services
provide. We run these experiments with an unoptimized NF (DVFS off) and an
optimized sender (DVFS off) and at different times of day to capture any
variance caused by time of day. We perform these experiments with an
unoptimized NF to see the viability of NFTY in the internet setting. The
sender and NF use the same nodes as the previous experiments, and the receiver
uses an Intel E-2288G processor with 8-core CPUs and 4.70 GHz frequency. Our
experiments utilize the 2-sided method.

NFTY-5K remains within 8% error in the Internet. Figure 11(a) shows that the
MdAPE for NFTY-5k in this setting never exceeded 5% for all NFs. For all 100
experiments for each NF, the calculated error never exceeded 8%. Thus, NFTY-5K
achieves very low error rates even in the Internet environment such that we
have DFVS disabled at the NF. We can also infer that, due to the closeness of
the MdAPE and maximum error, that there is little spread and variance of
NFTY-5K in the Internet. Thus, NFTY-5K proves itself as a reliable method
where noise and delays may be prevalent. Like our previous experiments, we
also see a general trend where the faster NFs have larger MdAPE results due to
more noise in the dispersion values when the packets are sent across the
Internet.
NFTY-100 results in less than 10% MdAPE for single-threaded NFs.  Figure 11(b)
indicates that NFTY-100 achieves low MdAPE values for the single-threaded NFs:
SNORT-RL, Suricata-RL, and Suricata-BL. None of these MdAPE values exceeded
6%, demonstrating the high accuracy that NFTY-100 can achieve in the Internet
setting with such a small amount of packets. Compared to the spread of the
Internet2 experiments, NFTY-100 has a greater spread (not shown in figure
11(b)) due to the added noise of the Internet. For the multi-threaded NFs,
there are two queues that packets are processed in, and so each queue
processes only 50 packets each. With so few dispersion values for each queue
and the noise of the Internet prevalent at the beginning of a probe, NFTY
produces an inaccurate estimate. Figure 11(a) indicates that using 5000
packets instead for NFTY produces far more accurate results that outweighs the
noise of the Internet that is prevalent in the first 100 packets of the probe.
Both NFTY-100 and NFTY-5K consistently outperform SLoPS. When comparing
performance of NFTY to SLoPS, it has a smaller MdAPE for all NFs for both
techniques. As seen in the results for the controlled environment and
Internet2, SLoPS performs poorly for the multi-threaded NFs. This is because
the threads are assigned to based on flow, and SLoPS sends all packets to only
one thread, thus predicts the processing capacity of only one queue. Although
NFTY-100 has reduced accuracy for the multi-threaded NFs, it still outperforms
SLoPS. When comparing performance for the single-threaded NFs, NFTY-100 cuts
the MdAPE by approximately 50%. For NFTY-5K, it’s performance is similar to
SLoPS’ for the single-threaded NFs but reduces MdAPE by at least 90% for the
multi-threaded NFs.

(a)

(b)

Figure 11:  (a) Comparing SLoPS-5K and NFTY-5K in internet experiments with an
optimized sender and unoptimized NF. (b) Same setting as (a), but now
comparing NFTY-100 and SLoPS-100.

[NFTY comparison with baseline in the Internet setting](a) Comparing SLoPS-5K
and NFTY-5K in internet experiments with an optimized sender and unoptimized
NF. (b) Same setting as (a), but now comparing NFTY-100 and SLoPS-100.

###  6.5 Case Study: NFTY against Commercial NF in the Cloud

Having tested NFTY in the lab and in the Internet we aim to investigate
whether our results generalize beyond open-access NFs and in-house
deployments. To this end, we use NFTY to calculate the capacity of the
Fortinet next-generation firewall[fortinet] which is a closed-source and
commercial NF.

Cloud setup: We deploy the Fortinet firewall in the AWS US East cluster on an
AWS c4.large instance type in front of a private subnet which was the
recommended instance type by the vendor. Thus, all traffic entering the subnet
passes through the firewall as we show in Figure10(a). We have configured the
firewall to use its default attack detection profiles for all UDP traffic. We
find the ground truth processing capacity to be 62738 pps. We measure the
ground truth using a local node within AWS by flooding the NF and measuring
the received rate at the receiver. We found that when we flood the NF, the
receiver constantly receives packets at a rate of 62738 pps, and the remaining
packets are dropped at the NF. We use our Clemson Cloudlab node to probe the
firewall using UDP traffic to implement NFTY-100. Observe that traffic from
Clemson to the AWS nodes is forwarded through the public Internet and, thus is
subject to cross-traffic.

We find that NFTY-100 can accurately estimate the processing capacity of the
Fortinet firewall within 7% error. The spread in the error is high, which
might be due to the the noise from use of a VM of either NF or the receiver
node 10(b). This shows that given an unknown NF with unknown deployment, NFTY
can accurately estimate its processing capacity.

##  7 Countermeasures

We present several countermeasures against an NFCR attack, which essentially
try to either conceal the dispersion values or the resources available at the
NF. We evaluate them for their effectiveness and the added overhead they
impose.

Adding a random delay: A network operator could add a random delay to packets,
to affect the measured dispersion and thus obfuscate the real NF processing
delay. While intuitive and simple, its not clear whether this countermeasure
will work in practice despite adding overhead to legitimate traffic since
adding random delays might still preserve the average dispersion, making an
NFCR attack feasible.

Additional packet batching:: Rather than releasing packets as they arrive, an
NF could buffer and release them in batches to change the dispersion
signature, and affect capacity estimation. The buffer size introduces a
tradeoff between effectiveness and added latency to legitimate flows.

Reorder using the multiple-queues: One could leverage multiple queues on NICs
to trigger packet reordering. By forcing packets of the same flow to be
sprayed across different queues, the attacker’s packets would arrive
reordered, effectively disrupting the dispersion signature. While this
countermeasure would not delay traffic, it will affect the TCP performance
which is known to suffer from reordering.

Rate-limiting: Another alternative is to make the NF appear to have lower
capacity, by rate-limiting packets from the same flow or IP source for
example. While an attacker mitigates this countermeasure by using multiple
IPs, this would again require her to deal with packet re-orderings and also
require keeping per-flow state which can be impractical. This countermeasure
will have low overhead, as a single flow should not use _even instantly_ the
full capacity of the NF.

Under-clocking the NF: An NF can set the parameters of DVFS governors to stay
at a lower frequency for longer and switch to higher frequencies after more
sustained loads. As NFTY sends a few thousand packets to trigger DVFS, with
this countermeasure, an attacker would need to send many more packets making
them detectable. However, delaying frequency scaling would process legitimate
traffic slower.

(a)

(b)

Figure 12:  (a) Under-clocking is the most effective countermeasure. (b)The
countermeasures impose overhead on legitimate traffic e.g., under-clocking
would decrease the throughput of a TCP flow by 0.72%.

[Performance of counter-measures]Under-clocking is the most effective
countermeasure. It would increase NFTY’s MAPE by 3x to 7x. (b)The
countermeasures impose overhead on legitimate traffic. For example, under-
clocking would decrease the throughput if a TCP flow by 0.72%.

Countermeasures evaluation: We investigate the trade-off between effectiveness
and overhead of these countermeasures. To do so, we measure the accuracy of
NFTY in estimating the capacity of three realistic NFs, with various
countermeasures deployed. To characterize overhead, we measure the loss in TCP
throughput for a single Iperf [tirumala1999iperf] flow. We perform $10$ runs
with each countermeasure and report the MdAPE and throughput reduction.

We simulate three countermeasures, excessive batching with a batch interval of
$300\mu s$, rate-limiting by 20%, and under-clocking. Batching aims at
blurring the measured delay between packets (dispersion); rate-limiting
permanently obfuscates the NF’s true capacity, while under-clocking hides it
for some time. We configure a batching interval of 500us, rate-limiting per
flow to 20% of the maximum bandwidth, and under-clocking by 100ms.

Figures 12(a), and 12(b) summarize our results. We observe that under-clocking
is the most effective countermeasure as it increases NFTY MdAPE error by 3 to
5 times, while also incurring the least overhead since the low-frequency
setting is only applicable for a short period.Note that, this result is
subject to our chosen overhead metric. Intuitively, the overhead of under-
clocking would have been higher if we used another metric _e.g.,_ tail flow
completion time.

Accurately evaluating the overhead of each trade-off is beyond the scope of
our paper. Instead, this section provides various practical countermeasures
that an operator could deploy based on their goals and the importance of their
NF.

##  8 Related Work

In this section, we discuss related works beyond the link-bandwidth
estimation, which we already compared with.

Reconnaissance and prevention: Prior work in network reconnaissance tries to
infer the topology of the network to construct attacks [kang2013crossfire].
Similarly, Samak et al. [samak2007firecracker] infer rules of a remote
firewall by sending carefully crafted probes. Ramamurthy et al.
[ramamurthy2008remote] uses mini flash crowds to estimate various bottlenecks
such as access bandwidth, CPU utilization, and memory usage of a server.
Salehin _et al._ [salehin2013scheme] aims at estimating the delay in the
networking stack of a server by sending packet probes. These works do not
perform reconnaissance for NF capacity and are thus orthogonal to our work. In
addition to reconnaissance techniques, many prior works aim at protecting
against reconnaissance attacks [jafarian2015effective, meier2018nethide,
achleitner2017deceiving].

NF capacity modeling: Multiple works aim at modeling NFs for various reasons,
_e.g.,_ predicting memory impact on contention [manousis2020contention],
generating adversarial workloads [pedrosa2018automated], or predicting
performance [iyer2019performance]. Such works are complementary to NFCR and
can be used to further optimize inference.

##  9 Conclusion

This paper presents the first formulation and feasibility analysis of Network
Function Capacity Reconnaissance (NFCR). While anecdotal data suggests that
attackers have used some form of NFCR to scout the resources of their victims
prior to actual DDoS attacks, such attempts are not documented, leaving
network operators unable to detect or mitigate them. To bridge this gap, we
put ourselves in the shoes of an attacker and investigate various probing
strategies, measurement infrastructures, and threat models. In doing so, we
constructed a practical tool catered to the NFCR problem, namely NFTY. We
identify and evaluate two representative NFTY configurations, namely NFTY-100
and NFTY-5K. NFTY-100 can accurately estimate the capacity of simple NF
deployments while being extremely stealthy. NFTY-5K is accurate under more
diverse NF deployments but has a larger network footprint. While less accurate
than NFTY-5K, NFTY-100 is still powerful enough to estimate the capacity of a
commercial NF deployed in AWS within 7% error. Finally, we present and
evaluate countermeasures against NFTY.