11institutetext:  United States Navy 22institutetext: United States Naval
Academy
22email<EMAIL_ADDRESS>33institutetext: Forțele Navale Române
44institutetext: Trail of Bits

# Adversarial Knapsack and Secondary Effects of Common Information for Cyber
Operations

Jon Goohs  11 Georgel Savin  2233 Lucas Starks  22 Josiah Dykstra  44 William
Casey  22

###### Abstract

Variations of the Flip-It game have been applied to model network cyber
operations. While Flip-It can accurately express uncertainty and loss of
control, it imposes no essential resource constraints for operations. Capture
the flag (CTF) style competitive games, such as Flip-It , entail uncertainties
and loss of control, but also impose realistic constraints on resource use. As
such, they bear a closer resemblance to actual cyber operations. We formalize
a dynamical network control game for CTF competitions and detail the static
game for each time step. The static game can be reformulated as instances of a
novel optimization problem called Adversarial Knapsack (AK) or Dueling
Knapsack (DK) when there are only two players. We define the Adversarial
Knapsack optimization problems as a system of interacting Weighted Knapsack
problems, and illustrate its applications to general scenarios involving
multiple agents with conflicting optimization goals, e.g., cyber operations
and CTF games in particular. Common awareness of the scenario, rewards, and
costs will set the stage for a non-cooperative game. Critically, rational
players may second guess that their AK solution—with a better response and
higher reward—is possible if opponents predictably play their AK optimal
solutions. Thus, secondary reasoning which such as belief modeling of
opponents play can be anticipated for rational players and will introduce a
type of non-stability where players maneuver for slight reward differentials.
To analyze this, we provide the best-response algorithms and simulation
software to consider how rational agents may heuristically search for
maneuvers. We further summarize insights offered by the game model by
predicting that metrics such as Common Vulnerability Scoring System (CVSS) may
intensify the secondary reasoning in cyber operations.

###### Keywords:

Knapsack Problem Game Theory Colonel Blotto Capture the Flag Flip-It
Adversarial Dynamics Adversarial Objectives Fictitious Play Agent Based
System.

##  1 Introduction and Motivation

Cyber attacks are characterized by unwilling and often unknown loss of control
of software, hardware, or services associated with networked data and devices.
At the same time, defense and offense operations are subject to resource
constraints. Given these constraints, attackers and defenders are required to
plan and allocate resource usage toward their objectives while leveraging any
informational asymmetries in their favor. Motivated to better understand
capture the flag (CTF) style competition games where players defend their
networks by patching vulnerable software and attack other networks by crafting
exploits of vulnerabilities, we seek to design realistic game theory to better
understand CTF and dynamic cyber operation scenarios in general. For players
to achieve objectives in these scenarios, several types of information become
important for planning: vulnerabilities, exploits, and patches. We describe
what these are in greater detail in section §3. For now, the basic attack
involves aiming an exploit against a specific vulnerability. The outcome
depends on the patch status of the vulnerability, if the vulnerable component
was unpatched the attack succeeds, otherwise the exploit will fail (when the
vulnerability was patched). The damage inflicted by a successful attack can
vary greatly, but depends on the vulnerability targeted. Additionally,
automation is common, where defenders can perform many patches and attackers
can perform many exploits with software tools.

Following prior work [13] that identifies the Weighted Knapsack as an
important tool for efficient resourcing for defense, we extend this reasoning
to include the attacker as they are subject to similar constraints and would
also seek efficient resourcing. But, then, the question becomes: if each
player is capable of solving the other’s knapsack problem (using intelligence
or common knowledge of its parameters), might a player deviate from
equilibrium attempting to out maneuver the other’s solution? We refer to this
type of strategic adjustment or second guessing as secondary effects. Here, we
extend the game theory to explore these secondary effects, in particular if
both player attempt to stay one step ahead of the others, what equilibria
results?

To understand this scenario we define a novel agent optimization problem
called Adversarial Knapsack . We illustrate how Adversarial Knapsack is the
essential game played at each time step within CTF or network control games,
more generally. Then, we resolve methodology to calculate the equilibrium pair
for each Adversarial Knapsack instance.

The mathematical analysis offers three insights. First, the underlying
combinatorial optimization problem and its reward landscape will offer
significant maneuvering options for players seeking reward differentials.
Secondly, common information such as metrics of vulnerability score and patch
cost, for which the Common Vulnerability Scoring System (CVSS) is an example,
intensify secondary reasoning. And thirdly, the effects of secondary reasoning
are limited by a cyclic algebraic structure arising in finite problems.

##  2 Background and Related Work

Platforms such as Hack the Box (HTB) [17] and King of the Hill [6] provide
students with the opportunity to practice cyber defense and penetration
testing within a safe sandbox environment. The general objective of these
platforms are to provide learning challenges for defense (patch and protect)
and offense (exploit and hack) within environments of virtual machines
networked in secure private networks. These systems offer practical instances
of real cyber security problems and mirror the essential challenges of cyber
security. Services such as HTB also offer competitive games such as capture
the flag (CTF) challenges where multiple players conduct both defensive and
offensive cyber operations within virtual networks. CTFs are used to test
operational skills, build teamwork, and advance organizational cyber security
posture [4] by developing skilled workforce of ethical hackers, pen testers,
and network defenders. These platforms also feature well developed video game
interfaces that attract a general audience, but strive to retain challenging
and timely complex problems. As such, they have been used for research [27]
and have emerged as recruitment systems for companies seeking a cybersecurity
work force to assess candidate skill level.

While many types of game theory have considered network control, we will focus
on two types closest to our presented model: Colonel Blotto games, and Flip-It
game forms. Colonel Blotto games, described by mathematician Émile Borel in
1921, were popularized within post WWII operations research science when the
game received its name [15]. These game theoretic ideas are common within
network, cyber-physical system, and radio spectrum security [16, 10, 24, 11,
28, 19]. Key to the Colonel Blotto game is that players have resource
constraints and have to solve a resource allocation problem to ready battle
fields, depending on the other player’s selected allocation, a sum is split
among the players and distributed. This notion of resource constraint is
important to manage the defensive and offensive resources during cyber
operations, for example in managing defense resources strategically [30, 22],
under denial of service attack [32], or specifically to neutralize
exploitation via patch planning [8, 13].

While Colonel Blotto captures the realistic notion of resource constraints in
cyber operations, it struggles to accurately model cyber operations in two
separate ways. First, the notion of conquering a resource is complex. Note
that some software vulnerabilities can lead directly to full access while
others lead to partial or no access. Rules that account for the vulnerability
and the access they provide can enable more realistic dynamics. Recently
vulnerability scoring systems, such as Common Vulnerability and Exposures
(CVE) and Exploit Prediction Scoring System (EPSS) [18], attempt to measure
the notion of risk or damage [25]. Our model incorporates rules and commonly
known hazard scores to be more realistic. Secondly, Colonel Blotto games
typically describe complete information scenarios, but many cyber operations
are performed in stealth mode, leading to uncertainties of machine states
which can be resolved with costly verification actions.

The Flip-It game developed by van Dijk et al. [31] in 2013 addresses the
important aspect of uncertain machine control state. While it models
operational costs that flip or audit control states, it does so without any
reasonable constraint. Flip-It has become widely used to model network control
problems [20, 21], but its lack of resource constraints impute limitations to
its realism. Recently, reinforcement learning for Flip-It scenarios have been
proposed [26, 14], but without resource constraints, an optimal solution may
not result in an actionable plan. We argue its important to optimize subject
to resource constraints.

Our model, like Flip-It , contains informational asymmetries for both attacker
and defender, however, we incorporate realistic resource budgets of Colonel
Blotto for each time step. Other researchers have considered this very same
combination, Zhang et al. [33] blend information asymmetry with resource
constraints to consider network control. however, they consider only one type
of attack and allow attackers complete information concerning defender
network. Our model improves upon those. First, we model all known attack types
via common vulnerability, patch and exploit databases. Multiple attacks in
cyber is an important characteristic and has been observed to yield
evolutionary solutions [7]. By accounting for many attack options, we
formalize a more realistic set of strategic objectives and identify the
associated combinatorial optimizations. Secondly, we allow defender to
maintain private information, such as patch status or even asymmetric
information such as deceptive honeypots. Our more realistic model, with
multiple vulnerabilities, inherent resource constraints and informational
asymmetries, is better suited to contribute to realistic studies of CTF games
and dynamic network control problems.

Various scoring systems for vulnerabilities have gained traction in network
defense. One example is the Common Vulnerability Scoring System (CVSS) that
measures three types of hazards, base, temporal, and environmental, on a scale
of 1-10 [12]. These measures provide critical security information on a range
of common vulnerability enumeration. These measures are intended to help
improve defensive decision making and planning, for example allowing
organizations to determine the need for specific patches or mitigating actions
to prevent attacks. However, information like this is also useful to
attackers. One timeless problem is the uncertainty of how releasing a Common
Vulnerability information will shift the attacker’s posture, whether it may
speed up attacker timeline driven by a need to ‘use it our loose it’ (once a
patch is released and widely distributed). Alternatively, patch releases may
shift attacker’s focus to other 0-day vulnerabilities. Still, other attackers
can use CVE information to design exploits, which remain effective so long as
there are unpatched vulnerabilities. To our knowledge, this paper presents the
first game theory equilibrium results that incorporate how commonly known
hazard scores such as CVEs effect the decision making for both rational
attacker and defender.

The Weighted Knapsack problem has a long history, first occurring in the late
19th century as a number partitioning problem, mathematician Tobias
Dantzig111Father of George Datzig known for the simplex method solving linear
programming problems. gave the problem its current name. The general Weighted
Knapsack decision problem is known to be NP-complete, when the weight
parameter is bounded the problem has efficient solutions with dynamic,
integer, or binary programming. Weighted Knapsack has been used within
encryption systems, however abandoned as users tended to select keys that
avoid the inherent hardness [23, 29, 5] and allowing efficient knapsack
solutions (for bounded weight) to crack the encryption. Weighted Knapsack
problems surface in CTF games in relation to efficient resource use [13],
similarly we use binary programming to solve instances of Weighted Knapsack .
Here, we consider that the attackers also solves a similar resource use
problem. Since common vulnerability information is known to both attacker and
defender, it will help both in planning, for the attacker this means effective
attack strategies. To consider this and the secondary effects of maneuvering
we define a variation of the Knapsack Optimization Problem called Dueling
Knapsack (DK). The problem aims to capture dual opposing goals for both
attacker and defender agents. Additionally, we design analysis tools as
algorithms, the main tool can update belief by re-weight and then resolve a
knapsack problem, and we indicate how this would be used to generate best
response in the Adversarial Knapsack problem for any given, yet fixed opponent
strategy. We can then use those tools to calculate a sequence of strategies,
corresponding to each player reasoning out the other player’s best response to
each re-weighted optimization problem. The sequence of strategies is a natural
framework for rational players to consider in fictitious play or via
simulation. We illustrate examples showing the sequence of best responses
strategies will cycles and identify a cycle length bound and discuss the
corresponding minimax strategies, game values and equilibrium for each zero-
sum time step.

Our main contributions are:

  * •

Improvement of model realism for network control games mixing the constraints
of Colonel Blotto and uncertainties of Flip-It . These improvements provide a
sound foundation to understand cyber operations.

  * •

Formalizing the Adversarial Knapsack problem as the essential optimization
problem related to the game played during each time step.

  * •

Analysis of the secondary effects of common knowledge. For Adversarial
Knapsack , we postulate that best response provides insights for how rational
players may maneuver as secondary effects. We provide an efficient algorithm
that calculates best response by re-weighing the original Knapsack problem.

  * •

We determine that the second order effects of Adversarial Knapsack are bound
to cycle and therefore limited, we provide a method to calculate reward
variation, suggest strategy maneuvers, and determine mixed minimax equilibrium
pairs and game value within the sequence of best responses.

##  3 Formal Model for Network Control, Cyber Operations, and Games

In this section, we expand the definition of vulnerabilities, patches, and
exploits and explain how they relate in cyber operations. We then formalize
the game theory for network control by defining time steps, networks, nodes,
temporal node states, control states and graph, topology, and agent action
spaces. We then detail the state update procedures, define agent utility,
resource constraints, and the constrained optimization problems.

A vulnerability can be thought of as either a fault or weakness in design or
operation that jeopardizes the desired security properties. Currently, several
organizations maintain voluminous listings of vulnerabilities, examples
include Common Vulnerability and Exposures (CVE) listing nearly 200K distinct
vulnerabilities. Exploits are repeatable scripts or codes that target a
specific vulnerabilities to achieve some level of system compromise.
Currently, hackers use multiple exploit libraries (contain databases of
exploit scripts), for example the Metasploit framework contains over 2,000
distinct exploit scripts. These exploit scripts can be used in a variety of
ways including: offensive cyber operations, defensive penetration testing, CTF
competitions, develop cyber operational tools, or facilitate criminal hacking
activities. Finally, patches are any code or component modifications that will
mitigate the hazards of a specific vulnerability, thereby once applied the
patch prevent exploitation.

Vulnerabilities, exploits and patches, relations and life-cycles: Usually,
code vulnerabilities are first discovered by developers or security
researchers as software bugs or fault conditions. Once known, knowledgeable
individuals can can develop exploits or patches which may or may not be
contributed to common knowledge. Generally, vulnerability information is
widely or commonly shared via efforts such as CVE, and developers can then
design patches which can be deployed to keep end users safe. However, hackers
can also use CVE information to design exploits. If all components are fully
patched, no exploits will be effective. If no components are patched, all
exploits targeting those components are effective if/when they are used. Once
a component is patched, at least one exploit is no longer effective. When
components are phased out and replaced by newer components: any patches or
exploits for the older component cease to be effective, and vulnerability
discovery and exploit generation must move on to consider the currently
deployed components. Basic cost structure: We will generally assume the cost
to develop an exploit or patch is much greater than (by one to two orders of
magnitude) the cost of applying a patch. Exploit development requires
understanding of the vulnerable component, developing patches may entail
complex side effects for systems and be costly to design. Generally, patch
deployment is simpler and lower in cost.

###  3.1 Game State

Let time be discretized as: $T=\\{t_{0}+k\delta:k\in\\{0,1,2,\cdots\\}\\}$,
with $\delta$ the largest appropriate time step required to model network
states. Throughout, we will use $k$ as the time step index. Let ${\cal
V}_{k}:=V=\\{v_{1},v_{2}\ldots v_{M}\\}$ be the set of network nodes at time
$k$. We will use a fixed set of nodes222In most dynamic graph problems, the
node set can be held constant, edges can have temporal dependence expressing
node gain and loss to the network.  for every time step $k$ and throughout we
use $j$ as the node index. Let ${\cal E}_{k}\subset{\cal V}\times{\cal V}$ be
the set of edges, $(v,w)\in{\cal E}_{k}$ if node $w$ is connected to node $v$
at time $k$. The edge set captures the momentary network topology333The
network graph provides all possible single-hop communications in the network,
whether utilized or not. The topology is a set of local neighborhood of
$v_{j}$ at time $k$ be defined as: ${\cal N}_{jk}=\\{w\in{\cal
V}:(v_{j},w)\in{\cal E}_{k}\\}$ for each node $j\in\\{1,\ldots,M\\}$.

Let $H=\\{h_{1},h_{2},\ldots,h_{N}\\}$ be a fixed set of vulnerabilities,
throughout we will use $i$ as the vulnerability index. Let

$\phi_{ijk}=\begin{cases}1\text{ if vul }i\text{ is present and unpatched on
node }j\text{ at time }k\\\ 0\text{ otherwise }.\end{cases}$

These zero-one indicator variables above determine the possible fronts where
an attack maybe effective at time step $k$. This information will be private
to the defender, but otherwise act like fields in a Colonel Blotto game (§2).

Network Control Graph: Within the dynamic scenario, we consider a set of
agents ${\cal A}=\\{a_{1},a_{2},\cdots a_{L}\\}$, and control function
$\Gamma:{\cal V\times T\times A}\rightarrow\\{0,1\\}$ that indicates the state
of control for each network node: $\Gamma_{jke}=1$, if node $j$ is controlled
by agent $a_{e}$ at time step $k$. Throughout, we will use $e$ for the agent
index. The control states $\Gamma$, as a global function will not be known to
any single agent, but only known to omniscient nature. In CTF games, the
control state is verified by an independent Scorebot agent [6]. For a single
machine $v_{1}$ and two players $\\{a_{1},a_{2}\\}$, the function
$k\rightarrow\Gamma_{11k}$ can be viewed as the control state of a Flip-It
game. Within our model, the true control state is unknown to players until
they attempt a patch action, analogous to audit or flip operations in Flip-It.
Similar to Flip-It , player actions may only provide momentary certainty
because the private actions of other players can change control states at any
time. For convenience we define: $\Gamma_{ji}$ to be the owner of node $j$,
that is $\Gamma_{ji}=\\{e:\Gamma_{jie}=1\\}$

Network Topology and instantaneous attack surface: Network topology is an
important control factor, and arise in security designs including layered
security, VPNs, and Firewalls. To demonstrate the minimax solution to the
static game, we defer the topological considerations for later and need only a
notion of boundary or reachable nodes. The zero one variables $r_{jk}$
indicate if a machine $j$ is reachable at time step $k$ (by any player).

###  3.2 Common Information

Vulnerability scoring systems are the de facto common knowledge of
vulnerabilities. We will assume a function $H_{i}$ that measures hazard of
vulnerability $i$. Additionally, we will assume a commonly known patch cost
function $C_{i}(x)=b_{i}+m_{i}x$ to reflect a tooling cost $b_{i}$ and unit
scaling cost $m_{i}$ to fix $x$ instances of vulnerability $i$. Also, we will
assume a commonly known attack cost function $d_{i}(x)=B_{i}+M_{i}$ which
likewise has tooling and scaling costs. We assume the average exploit cost
parameters to be one to two magnitudes greater than average patch costs,
however, in our simulations of random cost structure we generate each as
independent uniform values in a range.

We summarize the state variable in the game with table 1 below, and then
define decision spaces for players.

Parameters and State at time step $k$
---
rows are vuls | columns are machines/nodes |
patch cost | haz | vul | $1$ | $2$ | $3$ | $\ldots$ | $j$ | $\ldots$ | $M$ | v tot
$b_{1}$ | $m_{1}$ | $H_{1}$ | ${1}$ | ${\phi}_{11k}$ | $\phi_{12k}$ | $\phi_{13k}$ | $\ldots$ | ${\phi}_{1jk}$ | $\ldots$ | $\phi_{1Mk}$ | $z_{1k}$
$b_{2}$ | $m_{2}$ | $H_{2}$ | $2$ | $\phi_{21k}$ | $\phi_{22k}$ | $\phi_{23k}$ | $\ldots$ | $\phi_{2jk}$ | $\ldots$ | $\phi_{2Mk}$ | $z_{2k}$
$b_{3}$ | $m_{3}$ | $H_{3}$ | $3$ | $\phi_{31k}$ | $\phi_{32k}$ | $\phi_{33k}$ | $\ldots$ | $\phi_{3jk}$ | $\ldots$ | $\phi_{3Mk}$ | $z_{3k}$
$\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\ddots$ | $\vdots$ | $\iddots$ | $\vdots$ | $\vdots$
$b_{i}$ | $m_{i}$ | $H_{i}$ | $i$ | $\phi_{i2k}$ | $\phi_{i2k}$ | $\phi_{i3k}$ | $\ldots$ | $\phi_{ijk}$ | $\ldots$ | $\phi_{iMk}$ | $z_{ik}$
$\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\iddots$ | $\vdots$ | $\ddots$ | $\vdots$ | $\vdots$
$b_{N}$ | $m_{N}$ | $N$ | $h_{N}$ | $\phi_{N1k}$ | $\phi_{N2k}$ | $\phi_{N3k}$ | $\ldots$ | $\phi_{Njk}$ | $\ldots$ | $\phi_{NMk}$ | $z_{Nk}$
node totals | $\sigma_{1k}$ | $\sigma_{2k}$ | $\sigma_{3k}$ | $\ldots$ | $\sigma_{jk}$ | $\ldots$ | $\sigma_{Mk}$ | $Z_{k}$
control states | $\Gamma_{1k}$ | $\Gamma_{2k}$ | $\Gamma_{3k}$ | $\ldots$ | $\Gamma_{jk}$ | $\ldots$ | $\Gamma_{Mk}$ |
accessible | $r_{1k}$ | $r_{2k}$ | $r_{3k}$ | $\ldots$ | $r_{jk}$ | $\ldots$ | $r_{Mk}$ |
Table 1: Networks include static parameters for vulnerabilities, and variables
$\phi_{ijk}$ (mutable by controlling agent) that indicate the presence of
vulnerably $i$ on machine $j$ at time $k$. Additionally, the control state for
node $j$ at time $k$ is denoted $\Gamma_{jk}$ and will indicate the agent
control for the node. The values $z_{ik}$ represents the aggregate hazard of
vulnerabilities $i$ at time $k$. the values $\rho_{j}k$ represents the
aggregate hazard for node $j$ at time $k$. These settings and topology, will
determine the Colonel Blotto scenario occurring at each time point $k$.

In table 1, Machines (or nodes) are represented by columns $1$ through $M$,
and vulnerabilities are represented by rows $1$ through $N$. Vulnerabilities
will have static characteristics, including a hazard score $H_{i}$ for
vulnerability $i$, and a linear cost structure to patch instances:
$c_{i}(x)=b_{i}+m_{i}x$.

For a fixed hazard function that assigns $H_{i}$ to vulnerability $i$,
variables $\sigma_{jk}=\sum_{i=1}^{N}\phi_{ijk}H_{i}$, and
$z_{ik}=H_{i}\sum_{j=1}^{M}\phi_{ijk}$ will respectively represent the sum
hazard of machine $j$ at time $k$, and the sum hazard presented by
vulnerability $i$ at time $k$. The value
$Z_{k}=\sum_{j}\sigma_{jk}=\sum_{i}z_{ik}$ is the sum of all hazards due to
vulnerabilities within the network present at time $k$. In the next row, we
denote the control states variables $\Gamma_{jk}$. The final row will indicate
reachability of the node, or that it is within play reachable by attackers.
The control variables $\Gamma$ indicates the principal agent capable of muting
column entries of $\phi$.The defender (owner) $\Gamma_{jk}$ can for any
vulnerability mute $\phi_{ijk}$ from zero to one at time $k$ by patching the
vulnerable component, this operation will cost the agent according to the cost
structure of vulnerability $i$. Note we also formalize reversions, or patch
removal, thereby reintroducing a fixed vulnerability, meaning the owner can
mute an entry of $\phi$ from zero to one.

###  3.3 Player Roles and Action Space

Players can perform defense actions such as patching or changing a
vulnerability’s patch status, attack actions such as launching an exploit. A
patch action removes other player’s (attacker) ability to exploit the
vulnerability, and thereby blocks the attacker’s ability to flip the node if
they select that vulnerability to exploit. The patch status of any
vulnerability on any node of the defender’s network is private information,
only known to the agent controlling the node (i.e., defender). We use the
following indicator variables to indicate a defensive action:

$\zeta_{ijk}=\begin{cases}1\text{ if player changes patch status of vul
}i\text{ on node }j\text{ at time }k\\\ 0\text{ o.w. }\end{cases}$

The action $\zeta_{ijk}$ can only be performed by $\Gamma_{jk}$. Indicator
variables $\zeta_{ijke}$ can be used when the player acting $e$ needs to be
identified within the indicator function.

In attack, we will assume each player can remotely probe or scan reachable
nodes to determine software components but not its patch status. The player’s
action space will consist of selecting a machine and a vulnerability to deploy
an exploit against.

$\xi_{ijk}=\begin{cases}1\text{ if player attacks vul }i\text{ on node
}j\text{ at time }k\\\ 0\text{ o.w. }\end{cases}$

Indicator variables $\xi_{ijke}$ can be used to further indicate the attacking
player.

(a) Networks comprised of nodes, nodes comprised of components know to all
players

(b) Defender controls patch level privately, attack outcomes vary given patch
level

Figure 1: Attack and Defense Asymmetries: In Cyberspace, attackers have an
advantage that they only need to exploit one vulnerability, while defenders
must protect all vulnerabilities to remain secure. (a) Networks are comprised
of nodes. A node, owned by the defender, is a heterogeneous mix of software
components, each component is visible to all players. Components relate to
fields in a Colonel Blotto games, however the differ as well, as the attacker,
only needs one unpatched vulnerability to flip control of a node. (b) The
defender allocates defense resources to mitigate vulnerabilities by patching a
component, thereby removing an attacker’s exploitation possibility when
attacked. Note that only the defender knows the true patch state of each
component.

The cost of both types of actions were summarized in §3.2, and assumed to be
commonly known.

###  3.4 Game Dynamics

The game state at time $k$ is defined by the control states $\Gamma_{ik}$ for
$j\in\\{1\ldots M\\}$. The available actions depend on the subset of $V$
reachable (i.e., $\\{j:r_{jk}=1\\}$, (which can further be dependent on games
state and network topology).

At time step $k$, the defensive actions are first used to update the $\phi$
variables as:

$\phi_{ijk}=\phi_{ij(k-1)}\otimes\zeta_{ijk}.$ (1)

Note that the XOR operation will always flip the prior patch status444 Note
that to weaken components by reverting a patch status is a backdoor attack and
may be beneficial if it provides a means to re gain access a resource should
an it be lost..

Next, at time step $k$, we will consider attacks. Recall that $\xi_{ijke}$
will indicate that vulnerability $i$ is attacked on machine $j$ at time $k$ by
player $e$. The attack will cost a resource $d_{i}$, and will be successful if
$\phi_{ijk}=0$, or otherwise futile if $\phi_{ijk}=1$. A successful attack
will change the control state to that attacker, starting at time step $k+1$. A
futile attack will not change any control state. Taking into account the
actions of two players $e,e^{\prime}$, we denote the full update to control
states as:

$\Gamma_{jke^{\prime}}=\Gamma_{j(k-1)e^{\prime}}\otimes\phi_{ij(k-1)}\otimes\zeta_{ijke}\otimes\xi_{ijke^{\prime}}.$
(2)

###  3.5 Agent Rationality and Conflicting Interest

A scorebot rewards the player with a fixed reward $\mu$ for each unit of time
a player controls the node. While players derive utility from unreachable
nodes, reachable nodes at time step $k$ can potentially change control states,
so player actions at time $k$ can reallocate the fixed rewards offered by
reachable nodes. Said differently, at time step $k$, players are reallocating
control of ${\cal R}_{k}=\\{j:r_{jk}=1\\}$, letting $R_{k}=|{\cal R}_{k}|$,
players are reallocating $\mu R_{k}$ units of value at time step $k$. Players
who control a node can perform defensive patch actions with the purpose to
hold the node, while attackers will deploy exploits against ${\cal R}_{k}$
deemed most likely to change the nodes’ control states.

At time $k$, player interests over $\mu R_{k}$ units are completely opposed as
a successful attack results in a direct transfer of utility from defender to
attacker as in a zero sum quantity.

All player actions come at a cost, unlike Flip-It where players can invest
unlimited resources, we view constrained resource budgets for each time step
$k$ as more realistic. To patch a vulnerability takes resources (time and
cost), as does developing or deploying an exploit.

###  3.6  Utility Objectives and Resource Constraints

The utility of each player is an additive function aggregating time ownership
of nodes. Each node will yield a contested resource at each time step for
which its reachable. We make the more realistic assumption that utility is
sought under a fixed and bounded resource budget (per times step). Therefore,
players plan action sequences to maximize the utility subject to the resource
constraint.

$U_{e}(T)=\sum_{k=0}^{T}\sum_{j=1}^{M}\delta^{k}\mu_{j}\Gamma_{jke}\ \forall\
e\in{\cal A}$ (3)

Subject to the $k^{th}$ step resource limitation:

$\sum_{i=1}^{N}\sum_{j=1}^{M}\left(d_{i}\xi_{ijk}^{e}+c_{i}\zeta_{ijk}^{e}\right)\leq
C_{e}\ \forall\ k\in 1,\ldots T\ \forall\ e\in{\cal A}$ (4)

Here $\mu_{j}$ generally models node value differentials. And $\delta\in(0,1]$
is a standard future reward discount parameter used in Value Iteration
algorithms.

Rational agent will optimize their won individual objectives defined by
equations 3 subject to the system of constraints defined by equation 4, system
dynamic update given by equations 2, will comprise our model an agent based
system we term dynamic network control game.

###  3.7 Agent Based Model Summary

The novel dynamic network control game presented above resembles the
informational uncertainties of Flip-It , but refines the uncertainties to more
realistic forms: The attacker doesn’t know component patch state and neither
player will know the other’s plan. We additionally avoid the unrealistic
notion of unbounded budgets in Flip-It , and return to an earlier notion of
battling with constrained resources and bearing greater resemblance to the
Colonel Blotto game. From this direction refinements include use of private
information, and composition of components with a weakest link logic as it
only takes one (of the many heterogeneous software components) successful
exploit to flip the control state for any node. Our game posits agents as
constrained optimizer of utility, and defines a logically complete set of
update rules consistent with CTF games and adapted to the realism requirements
mentioned before.

##  4  Analysis and Methods

Analyzing play of the dynamic network control game, is a complex task due to
its many parameters, however several computational paths forward are feasible.
First, numerical and simulation based approaches are able to test and evaluate
a variety of agent strategies within specific environments, even those with
complex parameters derived from real world networks with software inventory
scanners and topological data. Secondly, simplifying assumptions can be
imposed to study specific cases and their resulting equilibrium. Furthering
this approach, a simulation and empirical game theory can assist to develop
mathematical insights. Here, we take the second route and consider simplifying
assumptions to deriving the Adversarial Knapsack problem and its special case
for two players confined to attacker and defender actions respectively we term
the Dueling Knapsack . We start by reviewing the original knapsack problem.

###  4.1 Weighted Knapsack

Many constrained optimization problems over binary variables can be reduced to
instance of a Weighted Knapsack problem. In Weighted Knapsack , there exists a
fixed set of $N$ objects having an associated weight $w_{i}$, and reward
$\mu_{i}$. An individual then selects objects to pack into a knapsack to
maximize the net reward while not exceeding a fixed weight limit $W$. Letting
$\theta_{i}$ be binary decision variables, the objective is the constrained
optimization problem:

$\max\sum_{i=1}^{N}\theta_{i}\mu_{i}\ \ :\ \ \sum_{i=1}^{N}\theta_{i}w_{i}\leq
W$ (5)

For uniform bound on the $W$, the Weighted Knapsack problem can be solved
efficiently for variables ${\bf\theta}$ using dynamic programming. For
increasing (unbounded) sequence in parameter $W$ the problem is known to
reduce NP-complete problems, and has no general efficient solution unless
$P=NP$. To address this, let ${\bf\theta}({\bf h},{\bf m},W)$ denote the
solution to equation 5, and let ${\tilde{\bf\theta}}({\bf h},{\bf m},W)$
denote the estimation of solution to equation (5) by feasible methods such as
the dynamic programming. We have not encountering difficulty by using dynamic
programming in the moderately sized network control problems our simulation
software generates. Thus, we observe that interesting network control problems
seem to be solvable efficiently using binary programming, including the
results shown for Dueling Knapsack .

###  4.2 Dueling Knapsacks

A particularly relevant special case of the dynamic network control game,
arising both in CTF as well as cyber operations, is when one player plays only
as defense while the other plays only as attacker. Let the Dueling Knapsack be
the special case with two agents $a,d$ that act strictly in attack and defense
mode respectively and play for a fixed time step $k$ (single round). That is
$\xi_{ijkd}=0=\zeta_{ijka}\ \forall\ i,j,k$. Note that for a single round, a
rational defender should restrict actions to applying patches not removing
them555Patch removal could be a viable option in CTF games where placing a
backdoor into a contested nodes can ease acquisition should the node be
compromised by another player. .

Letting, discount factor $\delta=1$, the first difference operator (in time)
$\Delta_{T}$ applied to the utility equation 3, represents the utility gained
by player $x$ for a fixed round starting at $T$ and ending at $T+1$ as:

$\Delta_{T}U_{x}=\sum_{j=1}^{M}\Gamma_{j(T+1)x}\mu_{j}=\sum_{j=1}^{M}\Gamma_{jTx}\left(\prod_{i}\xi_{i}^{a}(1-\zeta_{i}^{d})\right)\mu_{j}.$
(6)

The first is by definition of first difference, the second equality is
obtained by using the update function 2. Next, dispensing with the time index,
and noting that contended nodes are owned by the defender (i.e.,
$\Gamma_{jTd}=1$, and letting $\zeta_{i}^{a}$ and $\xi_{i}^{d}$ denote more
succinctly the actions of attacker $a$ and defender $d$, we derive:

$\Delta
U_{a}=\sum_{j=1}^{M}\left(\prod_{i}\xi_{i}^{a}(1-\zeta_{i}^{d})\right)\mu_{j}.$
(7)

From equation 7, the utility gradient for attacker $a$ and defender $d$ is a
zero sum (in complete conflict) for Dueling Knapsack . Said differently, any
gain by attacker comes as a loss from defender.

$\Delta U_{a}=-\Delta U_{d}$ (8)

By noting that agents seek to optimize utility and by assuming the product
found in equation 7 has a single factor, we can obtain the abstract Dueling
Knapsack problem.

###  4.3 Abstract Dueling Knapsack

For the Adversarial Knapsack problem, weights can generally be asymmetric or
different for different players. That is letting $w_{i}^{a}$ be the weight
when object $i$ is used during attack, and $w_{i}^{d}$ is the weight when
object $i$ is used during defense, its possible that
$w^{a}_{i}\not=w^{b}_{i}$. The attacker $a$ seeks to exploit un-patched
vulnerabilities, indicated by $\xi_{i}^{a}(1-\zeta^{d}_{i})$ . All exploits
deployed are subject to the attacker resource constraint.

$\max\sum_{i=1}^{N}\left(\xi^{a}_{i}\left(1-\zeta_{i}^{d}\right)\right)\mu_{i}:\sum_{i=1}^{N}\xi^{a}_{i}w_{i}^{a}\leq
W_{a}$ (9)

While the defender $e$ seeks to minimize the same sum by selecting patches
subject to their resource constraint:

$\min\sum_{i=1}^{N}\left(\xi^{a}_{i}\left(1-\zeta_{i}^{d}\right)\right)\mu_{i}:\sum_{i=1}^{N}\zeta^{d}_{i}w_{i}^{d}\leq
W_{d}$ (10)

Which is equivalent to:

$\max\sum_{i=1}^{N}\left(\zeta_{i}^{d}\xi^{a}_{i}\right)\mu_{i}:\sum_{i=1}^{N}\zeta^{d}_{i}w_{i}^{d}\leq
W_{d}$ (11)

This last form shows clearly the defender’s need to be precise selecting to
patch that which any attacker will next exploit666A multiplayer form of
Adversarial Knapsack problem can be developed along similar lines, in equation
9 the symbol $d$ can be replaced by $-a$ to indicated actions of any other
player, likewise in equations 10 and 11 the symbol $a$ could be replaced by
$-d$. .

The Dueling Knapsack problem can be constructed as either system of equations
9 and 10, or system of equations 9 and 11. Noting the assumption that each
node is comprised of one component $i=j$, the constraints player roles in
Dueling Knapsack , and that $w_{i}^{a},W_{a}$ correspond to $d_{i},C_{a}$,
while $w_{i}^{d},W_{d}$ correspond to $c_{i},C_{d}$, one can verify that
equations 3 and 4 reduce to the above system of equations 9 and 11.

We summarize the Dueling Knapsack optimization problem in table 2:

Dueling Knapsack (DK) Optimization
---
player | objective | mode | active resource constraint | solution
$d$ | $\min{\mathbb{E}}\left(\Delta U_{a}\right)$ | defender, $\xi_{ij}^{d}=0$ | $\sum_{i=0}^{N}w_{i}^{d}\zeta_{i}^{d}\leq W_{d}$ | patch plan: $\zeta^{e}$
$a$ | $\max{\mathbb{E}}\left(\Delta U_{a}\right)$ | attacker $\zeta_{ij}^{a}=0$ | $\sum_{i=0}^{N}w_{i}^{a}\xi_{i}^{a}\leq W_{a}$ | exploit plan: $\xi^{a}$
Table 2: In Dueling Knapsack the objectives for attacker and defender are
completely opposed. The defender seeks to minimize expected gains while the
attacker seeks to maximize them. Each must select a plan within resource
constraints.

###  4.4 Approximate Solution of Dueling Knapsack by Fictitious Play

As a zero sum game, the existence of a mixed strategy equilibrium is assured,
however for large $N$ its calculation can be shown to be prohibitive. Given
$N$, there are up to $2^{N+1}$ feasible outcomes. Both players, defender and
attacker, can select actions as up to $2^{N}$ binary assignments (so long as
they satisfy the weight constraints; i.e., equation 4). The convex
optimization problem required to calculate the equilibrium strategy is
therefore lengthy to formalize, much less solve. As such, each agent may
consider reducing the search by exploring best response to a variety of
plausible strategies the other may play.

Rational players first goal is to optimize utility. Due to the prohibitive
computational task, players will heuristically search, so search becomes an
important context for strategic reasoning, as players who can anticipate how
the other player search can maneuver. We refer to this type of reasoning as
secondary effects. To scrutinize a sequence of strategic maneuvers which
players consider, we define an update procedure for Dueling Knapsack and
utilize it to calculate best response given a peer’s strategy.

####  4.4.1 Fictitious Play

This type of reasoning involves fictitious play, and is performed by assuming
the other’s strategy, then updating equation 9, 10, then optimizing the
constrained optimization problem (eq 3 and 4). This method reduces the
computational requirements to a computationally feasible instance of Weighted
Knapsack . Thus, while solving for the game equilibrium (minimax strategy)
involves optimization over $2^{N+1}$ variables, fictitious play is a tool, and
will calculate best response by fixing an opponent strategy and solving an
instance of Weighted Knapsack problem that reduces to a binary programming
problem with $N$ variables. We next show that this approach is computationally
feasible and we detail the algorithms to calculate best responses for both
attacker and defender.

Given an opponent’s play (as a set of binary values), a player’s best response
is their choices (binary values) that optimize their objective. Let us observe
how the knapsack problem changes, given an opponents strategy. For example:
given that the defender strategy ${\bm{\zeta}}$ which may have involved
patching a fixed component $A$, (i.e., $\zeta_{A}^{d}=1$), the attacker’s best
response ${\bm{\xi}}$ should avoid attacking $A$ and any other vulnerability
that was patched, as it would be futile to attack component $A$, because its
payoff is neutralized by the defender action. This logic of avoidance can be
interpreted from the term $(1-\zeta_{A}^{d})$, in equation 9, as it introduces
a zero multiplier to $\mu_{A}$, thus the attacker budget would be better spent
on another component that remains un-patched. Conversely, the defender seeks
differently a logic of matching, as matching the actions of the attacker
introduce zero multipliers to 9, or alternatively yield nonzero multipliers in
11.

In any case the logic of best response for Dueling Knapsack has two phases:
First to update the objective function treating other player strategies as
data, next solve the Weighted Knapsack (constrained optimization problem) by
using dynamic programming. Attacker’s best response is calculated in algorithm
1, defender’s best response is calculated in algorithm 2:

Algorithm 1 Best-Response-A( ${\bf w,{\bm{\mu}}},W,{\bm{\zeta}}$)

$\langle{\bf w},{\bm{\mu}},W,{\bm{\zeta}}\rangle$ $\triangleright$ Given
costs/rewards, budget $W$, and defender strategy ${\bm{\zeta}}$

${\bf h}\leftarrow({\bf 1.-{\bm{\zeta}}}).*{\bf\mu}$ $\triangleright$ phase i,
update objective given defender choice

${\bf\xi}\leftarrow{\bf\theta}({\bf h},{\bm{w}},W)$ $\triangleright$ phase ii,
solve Knapsack and return Best Response as ${\bm{\xi}}$

Algorithm 2 Best-Response-D( ${\bf w,{\bm{\mu}}},W,{\bm{\xi}}$)

$\langle{\bf w},{\bm{\mu}},W,{\bm{\zeta}}\rangle$ $\triangleright$ Given
cost/rewards, budget $W$, attacker strategy ${\bm{\xi}}$

${\bf h}\leftarrow({\bm{\xi}}).*{\bf\mu}$ $\triangleright$ phase i, update
objective given attacker choice

${\bf\zeta}\leftarrow{\bf\theta}({\bf h},{\bm{w}},W)$ $\triangleright$ phase
ii, solve Knapsack and return Best Response as ${\bm{\zeta}}$

####  4.4.2 Extending Fictitious Play to estimate game value.

With the tools of best response, i.e., algorithms 1 and 2, effective
strategies can be generated as a type of virtual pre-play in preparation to
the game. Noting that another property of Zero Sum games is that at
equilibrium (minimax) the dual objectives match in value to the game value.
Thus, players who emulate the actions of their opponent can derive outcome
scores for both players to estimate the game value. Therefore, Fictitious play
can in some cases identify robust strategies or that certain strategies are
good enough (for example, a strategy whose safety level is within 8% of the
game value, could be considered good enough to justify looking no further). We
provide an example sequence of fictitious play.

###  4.5 Secondary Effects for Rational Agents in Dueling Knapsack

Strategic agents form strategies not only over problem parameters, but also
with respect to the strategies that other agents are likely to play. These
secondary effects involve optimization and maneuvering to the likely strategic
play of other agents. Here we show that they can determine a sequence of best
response strategic forms, and conclude with optimization of expected utility
given a belief probability of other player’s frequency of patch/exploit
actions.

During pre-play or planning, we illustrate the type of reasoning that
fictitious play facilitates. At step $0$, each agent could start with a simple
random (i.e., oblivious) strategy; that is, defense randomly select a set of
patches to apply until the resource constraint is exhausted, and likewise
offense likewise randomly selects a set of exploits until its resource
constraint is exhausted. Let $\zeta_{0},\xi_{0}$ represent these simple random
selection processes, which select components equally in probability.

As step $1$, both agents can reason that random strategies are a natural
starting strategy for the other, and so, each agent may seek improvements, by
optimization of one’s own resource use under the assumption that the other
randomly selects patches/exploits. For attacker, this means using common
knowledge ${\bf w},{\bm{\mu}}$, their own budget $W_{a}$ and setting
$\zeta=[1,1,\ldots,1]$, then calculating

$\xi_{1}=\text{{\sc Best-Response-A}}({\bf
w},{\bm{\mu}},W_{a},[1,1,\ldots,1]).$

Likewise for defender, a budget constrained hazard minimizing strategy uses
common knowledge ${\bf w},{\bm{\mu}}$, defense budget $W_{d}$ and setting
$\xi=[1,1,\ldots,1]$, then calculates

$\zeta_{1}=\text{{\sc Best-Response-D}}({\bf
w},{\bm{\mu}},W_{a},[1,1,\ldots,1]).$

Noting that the common knowledge also enables each player to solve the other’s
optimization problem, we further reason that players may maneuver in the
$k^{th}$ step. The attacker will have calculated $\xi_{k-1}$, but in an
attempt to stay a step ahead of the defender, will also calculate
$\zeta_{k-1}$ to see if maneuvering can result in a higher score with:

$\xi_{k}=\text{{\sc Best-Response-A}}({\bf w},{\bm{\mu}},W_{a},\zeta_{k-1}),$

Likewise, the defender will have calculated $\zeta_{k-1}$, but in an attempt
to stay a step ahead of the attacker, will also calculate $\xi_{k-1}$ to see
if maneuvering can result in a higher score with:

$\zeta_{k}=\text{{\sc Best-Response-A}}({\bf w},{\bm{\mu}},W_{a},\xi_{k-1}),$

Essentially, both players using computational have access to a sequence of
strategies that can be derived as best response during pre-play planning.
While at first these sequences may be constructed by players in attempts to
seek maneuvers to gain advantage. Introspective players will realize that
other rational introspective players will derive the same sequence. Let the
fictitious play path be the derived sequence:

$(\zeta_{0},\xi_{0}),(\zeta_{1},\xi_{1}),(\zeta_{2},\xi_{2}),\ldots$ (12)

and note that it can be considered a commonly known search path for the
prohibitive search for minimax strategy.

As such, the sequence may be understood as a measurement tool to mediate
outcomes in an otherwise prohibitive optimization task. Analysis of the game
may next turn to inference of game value, variation afforded to maneuvering,
sequence cycle length, attainment of game value within the sequence, and the
rates at which player’s can close in on game value by search. We illustrate
answers to these questions in the results section to follow.

In another type of analysis where expected rewards are optimized over belief
probabilities, the sequence in 12 can play an important roll, as it can be
used to estimate probability that players will patch/exploit any particular
option by using empirical frequencies. That is for attacker, let ${p_{A}}$ be:

${p_{A}}=\lim_{n\rightarrow\infty}\frac{\sum_{k}\zeta_{kA}}{n},$ (13)

where $\zeta_{kA}$ is the binary variable determining if defender patches $A$
for strategy $\zeta_{k}$. For defender, let ${q_{A}}$ be:

${q_{A}}=\lim_{n\rightarrow\infty}\frac{\sum_{k}\xi_{kA}}{n},$ (14)

We present the general expected optimization, given a belief probability over
the opponent’s patch/exploit frequencies as algorithms 3 and 4:

Algorithm 3 Expected-Optimal-A( ${\bf w,{\bm{\mu}}},W,{\bf p}$)

$\langle{\bf w},{\bm{\mu}},W,{\bf p}\rangle$ $\triangleright$ Given defender
probability ${\bf p}$ for patches.

${\bf h}\leftarrow({\bf 1.-{\bf p}}).*{\bf\mu}$ $\triangleright$ phase i,
update objective represents expected rewards given ${\bf p}$

${\bf\xi}\leftarrow{\bf\theta}({\bf h},{\bm{w}},W)$ $\triangleright$ phase ii,
solve Knapsack and return Expected Optimal as ${\bm{\xi}}$

Algorithm 4 Expected-Optimal-D( ${\bf w,{\bm{\mu}}},W,{\bf q}$)

$\langle{\bf w},{\bm{\mu}},W,{\bf q}\rangle$ $\triangleright$ Given attacker
probability ${\bf q}$ for port of attack

${\bf h}\leftarrow({\bf q}).*{\bf\mu}$ $\triangleright$ phase i, update
objective represents expected reward given ${\bf q}$

${\bf\zeta}\leftarrow{\bf\theta}({\bf h},{\bm{w}},W)$ $\triangleright$ phase
ii, solve Knapsack and return Best Response as ${\bm{\zeta}}$

##  5 Results

Our study of Dueling Knapsack concludes with insights from a process of
mathematical simulation. We discover two insights: first, that maneuvering
(considered in fictitious play) will cycle rather quickly. Second, we find
that players can use fictitious play to estimate game value and determine
reasonable strategies. Further, expectation maximization should tighten the
bounds for game value estimation even more. Taken together, these insights
suggest that while secondary effects may offer slight maneuverability for
players, they ultimately are not game changing.

###  5.1 Maneuvering and Estimating Game Value in Dueling Knapsack

To understand the special case of Dueling Knapsack , we design simulation
software written in the Julia programming language to generate random networks
composed of nodes comprised of vulnerable components. We use statistical
distributions to generate: vulnerabilities within components, random cost
structure for patching, and random cost structure for exploitation. To solve
knapsack instances, we use binary programming routines provided by JuMP [9].
We highlight several interesting deeper mathematical questions and summarize
the insights from simulating realistic size problems.

For the following discussion we generate networks of 100 machines, 70
vulnerabilities, Each node has a number of distinct vulnerabilities ranging
from zero to 10. The vulnerabilities are assigned hazard scores ranging
uniformly between 6 and 100. Patch cost distribution ranges uniformly between
100, and exploit development ranges uniformly between 100 and 700. And each
player has a fixed budget constraint of 800. We have not yet performed a wide
statistical sampling of all such configurations, however, we have generated
dozens of problem instances to observe the following characteristics.

####  5.1.1 Limited Maneuvering

Using our simulation approach, we find that the fictitious play sequence (12)
cycles rather quickly (see image 2(a)) even in large problems, thereby
suggesting limits to what a player can accomplish with maneuvering in Dueling
Knapsack . Theoretically, a cycle in assured due to the finite and discrete
nature of knapsack problems established by player selections of binary
variables. While we can bound cycle length to $2^{N+1}$, the total number of
actions available in the game, simulation suggests sequence 12 will cycle and
find limit cycle in only a few steps.

The cycle length and number of steps needed to enter the cycle may have a
statistical relationship to the distribution and parameters of networks. We
leave these broader questions open for future work, but comment here on some
intuitive aspects of networks which can help form insights as to why cycles
are small and quick to come by.

First, constraints make some actions infeasible, interesting problems will
engage the constraints, thus ruling out infeasible actions because all
strategies in the fictitious play sequence are required to be feasible. Thus,
the constraints reduce the bound on cycle length. Secondly, interesting
problems will also feature variation in costs, and hazards, and variation will
induce priorities for both utility seeking players. Said differently,
variations in parameters assure variation in utility and sparsity of the best
responses, therefore rational players will never elect to put poor performing
strategic options into a fictitious sequence, thereby reducing cycle length
dramatically. Still interesting mathematical questions arise, such as how
parameters of networks can relate to sparsity of the best responses.

(a) cycling strategic sequence

(b) Payoff matrix

Figure 2: Bounding the Secondary effects and how agents may utilize common
knowledge in fictitious play. We generated networks with 100 machines, 70
vulnerabilities, and calculate the fictitious play sequence starting from
random strategies. Generally, as in the image above, we observe that
fictitious play cycles within a few steps. In (a) we illustrate an example
strategy sequence cycling, each node represents a distinct tuple of strategies
identified by binary variable selection for $2^{N+1}$ variables. In (b) we
collect and visualize the payoff outcomes of all pairs $7\text{Chose}2$
strategies discovered in part (a). The associated zero-sum payoff matrix can
provide both players a means to estimate game value.

####  5.1.2 Estimation of Game Value

Zero-sum games admit to a mixed strategy equilibrium where the attacker
minimax strategy (optimizer of equation 9) value equals that of the defender
maximin strategy (optimizer of equation 10) value, the matching value is
termed the game value at equilibrium. While exploration of all strategies
remains computationally infeasible, the fictitious play sequence can be used
for exploratory search, and the payoffs can be evaluated using all pairs of
strategies discovered along the fictitious play path (see image 2(b)). Given
the need for sampling strategies, players could generate simulated play among
sampled strategies and perform standard analysis of the game based on the
limited sample. Standard Zero-Sum game analysis such as calculation of a
strategy’s saftey level, defined to be minimum score (for attacker) that an
attacker strategy can ensure, and the maxiumum score (for attacker) that a
defender strategy can yield, could be applied to the sampled strategies, done
in figure 3. Interestingly, both sides can determine strategies within $7.5\%$
of game value, arguably good enough given the computational infeasibility of
exhaustive search.

Figure 3: Strategic Stabilization at Maximin: Zero sum games have always have
mixed strategy equilibrium, but may also have pure equilibrium’s when maximin
and minimax are equal. In this example, where analysis is restricted to
strategies discovered with fictitious play the attacker has a maximin strategy
to guarantee a gain of $40$ nodes (or more), the defender can guarantee a loss
of no more than 43. These values bound the game value and can be used to
evaluate and optimize network designs for cyber security. These values
represent relative difference of less than 7.5% of game value.

One additional method which players can use to tighten the estimate bounds for
game value would entail calculating frequencies in which each component is
patched/exploited in fictions play by using equations 13 and 14, convergence
is assured by our earlier observation that fictitious play sequence (equation
12) cycles. Moreover, small cycle length further expediates convergence rate.
Using these estimated frequency values, algorithms 3 and 4 can be used by
attacker and defender respectively to calculate mixed strategies.

###  5.2  Dueling Knapsack Application to Cyber Operations

The Dueling Knapsack problem is closely related to the momentary
considerations during cyber operations and CTF competitions. Generally, it
models the tasks of offense and defense are divided into separate concerns and
captures the usual case of defense of a fixed network while offense attempts
to compromise any reachable nodes. Reachability and component enumerations can
be performed by scanning tools that conduct node and software component
inventory. Vulnerability inventory assessments and patch management also have
automating tools, as well as automated exploit generation and penetration
testing to estimate problem parameters. Weights and costs increasingly is
becoming common information Common Vulnerability Exposure (CVE) and other
metric sources can be used to form commonly known hazard scores $\mu$ and cost
functions ${\bf w^{a},w^{d}}$.

###  5.3 Simulation and Decision Support Software

While Dueling Knapsack provides intuition for a single stage in these games,
the dynamic game form is far more complex. Like in the Dueling Knapsack
problem, the role of fictitious play and simulation offer interesting
possibilities for the complex dynamic agent based game model presented herein.
Modeling networks is not difficult as their formal descriptions using graphs,
hazards and costs can generate Agent Based System Models, and the Adversarial
Knapsack game of equation 3 and 4. Therefore, we see a role for software that
considers fictitious play and simulation to form tools to explore strategic
actions in cyber operational scenarios. Below in figure 4 we show how software
tools which consider optimization strategy more generally could work.

(a) Initial game state

(b) One time step later

Figure 4: Encoding the networks into the game model can be automated, In (a) a
random initial game state is provided, it enumerating machines and
vulnerabilities along with associated hazard and costs for exploit/patch, in
(b) we observe the effects of player actions: ’+’ indicates flipped control
states, ’($x$)’ indicates patch actions on $x$, ’[$y$]’ indicates exploit
actions attempt on $y$. Notice that game states are updated to enable
simulation and evaluation of multi-step strategies.

###  5.4 Summary

We envision several applications of decision support software employing
simulation of Adversarial Knapsack . First, as a measurement tool, simulation
can be used to evaluate game outcomes in a variety of ways, including for a
specified network subset and software component configuration. As such, it
provides a design and assessment tool which allows a network engineer to
consider the vulnerability surface at each potential stage of a network
attack. Applying Adversarial Knapsack can determine effects of different
network typologies, or evaluate security hardened postures, such as minimizing
or containing services.

Second, this methodology can be applied in dynamic scenarios such as cyber
operations or within CTF game competitions. In this capacity, the methodology
enables fictitious play where operators could potentially play out several
moves into the future to evaluate simulated possibilities, or possibly even to
receive decision assistance. One aspect of this type of application and a
direction we plan to explore in the near future work will involve educational
support tools which may help cyber operators learn more effective use of
resources.

###  5.5 Simulation Code

We attach our code in the appended materials. Our program has been run on very
large simulated networks with thousands of nodes and vulnerabilities. Little
prevents the code from working on actual network data when encoded using
standard data structures of graphs and maps. In our simulations the
vulnerability scores, costs $w^{d},w^{a}$ are generated using statistical
distributions. As future work, we plan to apply this program to the use case
of vulnerability scanners such as Nessus [2] and OpenVAS vulnerability scanner
[3]. Additionally, we assert the use of CVSS scores [1] will increase the
accuracy of these values.

##  6 Conclusion

Stemming from research showing how combinatorial optimizations (such as
solving instances of Weighted Knapsack ) can result in better patch planning,
we set out to extend the same type of reasoning to the attacker objectives.
Commonly known to all agents are hazard scores associated with
vulnerabilities, as well as their patch (remediation) and exploit costs. This
information provides important and realistic information about the risks that
certain vulnerabilities have within systems, and would naturally be leveraged
by all agents in planning defense and attack. Common knowledge and common
awareness of the same raises a simple but basic question of secondary
reasoning: if each player is capable of solving the other’s knapsack problem,
might they attempt to out maneuver the other’s solution? We resolve this
question by formalizing agent based models for network control, which feature
bounded resources such as Colonel Blotto and information asymmetric aspects
such as Flip-It . Then, we capture the single time step game as instances of a
novel distributed optimization problem we term Adversarial Knapsack and the
special case of Dueling Knapsack . To evaluate the secondary effects at play
in Dueling Knapsack , we develop an analysis tool that calculates best-
response reducing it to instances of knapsack. Using this tool, we can expand
the chain of secondary reasoning, collecting strategies that could be
considered in fictitious play. We determine that the secondary reasoning
offers limited maneuvering, as best responses in fictitious play eventually
cycle and loop back into previously explored strategies. Cycles are explored
and found to occur rather quickly, thereby bounding the strategic options but
also offering a means to estimate game values and the possibility of
identifying reasonable strategies.

The model and methodology can be applied to design problems as well as
decision support systems, however that remains as future work. Perhaps another
interesting question that the model suggests is the use of misinformation.
Given that individual capabilities and costs structures naturally vary, a
question becomes how might errors or even manipulated common knowledge affect
Adversarial Knapsack and what are the implications for the single time step
game let alone the dynamic one. Another means to asking a related question, is
by adding noise and distortion to game data as well as considering agent
intentional noise such as trembling hand strategies. Additionally, many
interesting mathematical questions for Adversarial Knapsack equilibria arise
and remain open: What are the statistics of cycle length, and how do they
depend on distributions (of hazards, costs of patching and exploiting)? How do
they depend on the distribution of vulnerabilities within networks or even
network topological aspects? These questions may seem to offer limited
resolution in small networks, but how might they scale in larger networks?

While we focused on the impact of common information such as CVE scores, this
approach could be extended to consider situations where one player has non-
public intelligence about the opponent to solve their knapsack problem.
Research in this direction could help calculate the value of such
intelligence. Conversely, an expanded model could quantify the defensive value
of non-public information, such as being able to patch a novel vulnerability
that is not yet known to the opponent.

## References

  * [1] Common Vulnerability Scoreing System SIG.  https://www.first.org/cvss/.  Accessed: 2023-11-29.
  * [2] Nessus Vulnerabilty Scanner.  https://www.tenable.com/products/nessus.  Accessed: 2023-11-29.
  * [3] Open Vulnerability Assessment Scanner.  https://www.openvas.org/.  Accessed: 2023-11-29.
  * [4] Capture The Flag 101.  CTF 101.  https://www.ctf101.org, 2022.
  * [5] René Beier and Berthold Vöcking.  Random knapsack in expected polynomial time.  Journal of Computer and System Sciences, 69(3):306–329, 2004.
  * [6] Kevin Bock, George Hughey, and Dave Levin.  King of the hill: A novel cybersecurity competition for teaching penetration testing.  In 2018 USENIX Workshop on Advances in Security Education (ASE 18), 2018.
  * [7] William Casey, Rhiannon Weaver, Leigh Metcalf, Jose Andre Morales, Evan Wright, and Bud Mishra.  Cyber security via minority games with epistatic signaling.  In Proceedings of the 8th international conference on bioinspired information and communications technologies, pages 133–140, 2014\.
  * [8] Huseyin Cavusoglu, Hasan Cavusoglu, and Jun Zhang.  Economics of security patch management.  In Workshop on Economics of Information Security (WEIS 2006). Citeseer, 2006.
  * [9] Iain Dunning, Joey Huchette, and Miles Lubin.  Jump: A modeling language for mathematical optimization.  SIAM Review, 59(2):295–320, 2017.
  * [10] S Rasoul Etesami and Tamer Başar.  Dynamic games in cyber-physical security: An overview.  Dynamic Games and Applications, 9(4):884–913, 2019.
  * [11] Aidin Ferdowsi, Walid Saad, Behrouz Maham, and Narayan B Mandayam.  A colonel blotto game for interdependence-aware cyber-physical systems security in smart cities.  In Proceedings of the 2nd international workshop on science of smart city operations and platforms engineering, pages 7–12, 2017.
  * [12] Laurent Gallon and Jean-Jacques Bascou.  Using CVSS in attack graphs.  pages 59–66, 2011.
  * [13] Jonathan Goohs, Ray Mier, Paul Deist, and William Casey.  Reducing attack surface by learning adversarial bag of tricks.  In Workshop on Economics of Information Security (WEIS 2022), 2022\.
  * [14] Laura Greige and Peter Chin.  Reinforcement learning in flipit.  arXiv preprint arXiv:2002.12909, 2020.
  * [15] Oliver Gross and Robert Wagner.  A continuous colonel blotto game.  Technical report, Rand Project Air Force Santa Monica Ca, 1950.
  * [16] Abhishek Gupta, Galina Schwartz, Cédric Langbort, S Shankar Sastry, and Tamer Bařar.  A three-stage colonel blotto game with applications to cyberphysical security.  In 2014 American Control Conference, pages 3820–3825. IEEE, 2014\.
  * [17] Hack The Box.  Hack The Box: Hacking Training For the Best.  https://www.hackthebox.com, 2022.
  * [18] Jay Jacobs, Sasha Romanosky, Octavian Suciu, Ben Edwards, and Armin Sarabi.  Enhancing vulnerability prioritization: Data-driven exploit predictions with community-driven insights.  In 2023 IEEE European Symposium on Security and Privacy Workshops (EuroS&PW), pages 194–206. IEEE, 2023.
  * [19] Mina Labib, Sean Ha, Walid Saad, and Jeffrey H Reed.  A colonel blotto game for anti-jamming in the internet of things.  In 2015 IEEE global communications conference (GLOBECOM), pages 1–6. IEEE, 2015.
  * [20] Aron Laszka, Gabor Horvath, Mark Felegyhazi, and Levente Buttyán.  Flipthem: Modeling targeted attacks with flipit for multiple resources.  In International Conference on Decision and Game Theory for Security, pages 175–194. Springer, 2014.
  * [21] Zhaoxi Liu and Lingfeng Wang.  Flipit game model-based defense strategy against cyberattacks on scada systems considering insider assistance.  IEEE Transactions on Information Forensics and Security, 16:2791–2804, 2021.
  * [22] Dale McMorrow.  Science of cyber-security.  Technical report, The MITRE Corporation, 2010.
  * [23] Ralph Merkle and Martin Hellman.  Hiding information and signatures in trapdoor knapsacks.  IEEE transactions on Information Theory, 24(5):525–530, 1978.
  * [24] Minghui Min, Liang Xiao, Caixia Xie, Mohammad Hajimirsadeghi, and Narayan B Mandayam.  Defense against advanced persistent threats: A colonel blotto game approach.  In 2017 IEEE international conference on communications (ICC), pages 1–6. IEEE, 2017.
  * [25] Nuthan Munaiah and Andrew Meneely.  Vulnerability severity scoring and bounties: Why the disconnect?  In Proceedings of the 2nd International Workshop on Software Analytics, pages 8–14, 2016.
  * [26] Lisa Oakley and Alina Oprea.  Qflip: An adaptive reinforcement learning strategy for the flipit security game.  In International Conference on Decision and Game Theory for Security, pages 364–384. Springer, 2019.
  * [27] Georgel M Savin, Ammar Asseri, Josiah Dykstra, Jonathan Goohs, Anthony Melaragno, and William Casey.  Battle ground: Data collection and labeling of ctf games to understand human cyber operators.  In Proceedings of the 16th Cyber Security Experimentation and Test Workshop, pages 32–40, 2023.
  * [28] Galina Schwartz, Patrick Loiseau, and Shankar S Sastry.  The heterogeneous colonel blotto game.  In 2014 7th international conference on NETwork Games, COntrol and OPtimization (NetGCoop), pages 232–238. IEEE, 2014.
  * [29] Adi Shamir.  A polynomial time algorithm for breaking the basic merkle-hellman cryptosystem.  In 23rd Annual Symposium on Foundations of Computer Science (SFCS 1982), pages 145–152. IEEE, 1982.
  * [30] Walt Tirenin and Don Faatz.  A concept for strategic cyber defense.  In MILCOM 1999. IEEE Military Communications. Conference Proceedings (Cat. No. 99CH36341), volume 1, pages 458–463. IEEE, 1999.
  * [31] Marten Van Dijk, Ari Juels, Alina Oprea, and Ronald L Rivest.  Flipit: The game of “stealthy takeover”.  Journal of Cryptology, 26(4):655–713, 2013.
  * [32] Dong Wang, Zidong Wang, Bo Shen, Fuad E Alsaadi, and Tasawar Hayat.  Recent advances on filtering and control for cyber-physical systems under security and resource constraints.  Journal of the Franklin Institute, 353(11):2451–2466, 2016.
  * [33] Ming Zhang, Zizhan Zheng, and Ness B Shroff.  Stealthy attacks and observable defenses: A game theoretic model under strict resource constraints.  In 2014 IEEE Global Conference on Signal and Information Processing (GlobalSIP), pages 813–817. IEEE, 2014.


∎

11institutetext: Marcos A. Madrid: Dpto. Ingeniería Mecánica, Facultad
Regional La Plata, Universidad Tecnológica Nacional, CONICET, Av. 60 Esq. 124,
1900 La Plata, Argentina. E-mail<EMAIL_ADDRESS>
L. A. Pugnaloni: Dpto. Ingeniería Mecánica, Facultad Regional La Plata,
Universidad Tecnológica Nacional, CONICET, Argentina. Current address: Dpto.
Física, FCEyN, Universidad Nacional de La Pampa, Uruguay 151, 6300 Santa Rosa,
La Pampa, Argentina. E-mail<EMAIL_ADDRESS>
# Velocity profiles in forced silo discharges

Marcos A. Madrid  Luis A. Pugnaloni

(Received: date )

###### Abstract

When a granular material is freely discharged from a silo through an orifice
at its base, the flow rate remains constant throughout the discharge. However,
it has been recently shown that, if the discharge is forced by an overweight,
the flow rate increases at the final stages of the discharge, in striking
contrast to viscous fluids [Madrid et al. Europhys. Lett. (2018)]. Although
the general mechanism that drives this increase in the flow rate has been
discussed, there exist yet a number of open questions regarding this
phenomenon. One such questions is to what extent is the internal velocity
profile affected, beyond the trivial overall increase consistent with the
increasing flow rate. We study via Discrete Element Method simulations the
internal velocity profiles during forced silo discharges and compare them with
those of free discharges. The changes in velocity profiles are somewhat
subtle. Interestingly, during free discharges, while the velocity profiles are
steady at the silo base and above a height equivalent to one silo diameter,
there exists a transition region where the profile evolves in time, despite
the constant flow rate. In contrast, forced discharges present steady profiles
at all heights of the granular column during the initial constant flow phase,
followed by an overall increase of the velocities when the acceleration phase
develops.

††journal: Granular Matter

##  1 Introduction

The discharge of granular materials through an orifice at the bottom of a silo
is a phenomenon profusely studied (see for example [1; 2; 3; 4; 5; 6; 7]).
This is in part due to the technological interest of the problem, but also
because the significant challenges the scientific community has encountered in
predicting basic quantities such as flow rate and wall pressure during
discharge. The flow rate can be calculated by using the empirical Beverloo
equation [6]. However, there is not a full theoretical derivation of this
equation based on first principles. The main features of the Beverloo equation
are explained by heuristic postulates such as the _free fall arch_ and the
_empty annulus_ [5; 7]. Bottom pressure and wall pressure during discharge is
also poorly understood. It is often assumed that the Janssen equation [8; 9]
can predict the internal pressure under flowing conditions, despite a number
of experiments demonstrating that this is not the case [10; 11; 12] and a few
attempts to expand the Janssen approach to flowing silos [13; 14; 15; 16].

A remarkable feature of free granular discharges is the constant flow rate
observed despite the drop in the height of the granular column. This is in
contrast with viscous fluids, which show a decreasing flow rate as the level
of the container falls. It is also surprising that the flow rate seems to be
rather insensitive to the details of the grains properties (friction, elastic
modulus, poison ration, etc.). However, this is somehow consistent with
viscous fluids where the flow rate through an orifice on a plate does not
depend on its viscosity [17].

Figure 1: (a) Particle flow rate $Q$ as a function of the column height $h$
for various overweights $W$ (see legend). $Q$ is scaled by the Beverloo flow
rate ($Q_{\rm B}$). (b) Bottom pressure during the discharge. The vertical
lines correspond to the different column heights $h_{\rm fill}$ along the
discharge for which we have measured the various velocity profiles. Inset:
Column height $h^{\prime}$ at which the acceleration phase starts as a
function of the overweight $W$ (note the log-lin scale). Figure 2: Vertical
velocity heat map, $v_{z}(r,z)$, of the silo at different stages of the
discharge (different $h_{\rm fill}$) for a free discharge (left) and for a
forced discharge with an overweight of $W=114W_{\rm D}$ (right). Note that
only the right half of the silo is shown. The labels $h_{\rm fill}$ on each
figure indicate the point at which the heat map has been extracted during the
discharge according to the vertical lines indicated in Fig. 1(a). The
horizontal red lines indicate the position $z=z_{\rm view}$ at which profiles
are measured in the rest of the paper.

Recently, it has been shown that the use of an overweight on top of the
granular column of a discharging silo induces an increase of the flow at the
final stages of the discharge [18]. This is once again in contrast to viscous
fluids since these decrease their flow rate during discharge from a tank even
if a constant overpressure is applied to the free surface. More striking,
however, is the fact that the increase in granular flow rate does depend on
the grains material properties, which has no parallel effect in the case of
viscous fluids. The increase in flow rate using an overweight is indeed an
unexpected feature. Common wisdom among specialized scholars indicates that “…
it is pointless to try to extrude a granular material through a converging
passage by the application of a stress.” as stated in page 304 of Ref. [7].
However, experimental observations are against this prediction [18].

One may expect that the use of an overweight is equivalent to the addition of
extra granular material on top of the original granular column. However, any
additional granular material will contribute to the dissipation of energy
during the discharge due to the nonconservative particle–particle and
particle–wall interactions. A solid overweight operates differently since it
lays a constant weight on the free surface of the granular column and does not
dissipate energy except for the particle–overweight nonconservative contacts.

The basic mechanism to explain the increase in flow rate due to an overweight
is based on energy balance [18]. In a dense granular system, the collision
rate is very high, which leads to _inelastic collapse_. Therefore, all the
power injected by gravity during the discharge of a silo is continuously
dissipated. As a consequence, the discharge proceeds at constant velocity
since the energy input cannot be converted into kinetic energy. Since the
number of collisions per unit time is so large, all the energy is dissipated
even if the material properties are varied. This renders the flow rate
material independent. When a piston does work on the system at a high rate,
the collisions are unable to fully dissipate the energy input, particularly
when the number of particles in the column decreases. As a result, the flow
rate increases due to the non-dissipated injected power that is converted into
kinetic energy.

Due to the increase in flow rate, the mean velocity inside the silo increases
in the final phase of the discharge of a forced silo. However, one may expect
that the internal velocity profile is not simply upscaled but changed in a
more complex way. This becomes an important piece of information when it comes
to applications. Mass flow and funnel flow patterns are desirable/undesirable
depending on the applications. In this work, we focus on the velocity profiles
inside a discharging silo and compare free discharges with forced discharges.
We find a previously unnoticed behavior where free discharges present unsteady
velocity profiles in some regions of the silo, while forced discharges present
a more steady profile throughout the silo during the initial stages before the
flow rate increases. During the phase of flow rate increase, the forced flows
tend to flatter profiles in comparison with free discharges.

Figure 3: Scaled vertical velocity $v^{*}_{z}(r)=v_{z}(r)/v_{z}(z=0,r=0)$ at
various heights $z_{\rm view}$ (as indicated in Fig. 2) and for the different
column heights $h_{\rm fill}$ during the discharge. Results for different
overweights are compared in each plot: free discharge (blue), $W=4W_{\rm D}$ g
(orange), $W=20W_{\rm D}$ (purple), $W=35W_{\rm D}$ (red) and $W=114W_{\rm D}$
(green). Each row corresponds to a different observation plane $z_{\rm view}$
in the silo, while each column corresponds to a different column height
$h_{\rm fill}$ during the discharge. Inset: Sample of the velocity profile
before scaling.

##  2 Simulations

We use Discrete Element Method (DEM) simulations via the LIGGGHTS [19]
implementation with a particle–particle Hertz interaction and Coulomb
criterion using a Young modulus $Y=70$ MPa, Poison ratio $\nu=0.25$,
restitution coefficient $e=0.95$ and friction coefficient $\mu=0.5$ [19]. The
same interaction applies for the particle–wall contacts. Particles are
spherical with diameter $d=1$ mm and density $\rho=2500$ kg/m3. The silo is
formed by a cylinder of diameter $D_{\rm s}=2R_{\rm s}=30$ mm. The base of the
silo is flat and has a circular orifice of diameter $D=15$ mm in its center.
For the forced flow simulations, we introduce as an overweight a cylindrical
piston with the desired weight $W$. Particles are poured to fill a height in
the silo above $12D_{\rm s}$ (which implies up to $3\times 10^{5}$ grains).
The bulk volume fraction obtained is $\rho_{\rm b}=1500$ kg/m3. The orifice is
initially blocked by a plug. After the grains come to rest in the silo (we
wait until the kinetic energy per particle falls below $5\times 10^{-12}$ J),
we remove the plug and allow its discharge. The acceleration of gravity is
$g=9.81$ m/s2 and the time step $5\times 10^{-6}$ s. We measure the overweight
in terms of the typical weight $W_{\rm D}$ of a column of grains of height
$D_{\rm s}$, i.e., $W_{\rm D}=2\pi R_{\rm s}^{3}\rho_{\rm b}$.

To assess the velocity and pressure profiles at different stages of the
discharge we save snapshots with the particle positions, velocities and
contact forces every $5\times 10^{3}$ time steps (i.e., $40$ fps). We average
properties over snapshots grouped by the number of grains that remain in the
silo (in blocks of $1\times 10^{4}$ particles). This allows us to compare
discharges having different flow rates (free and forced discharges) by putting
side by side data that correspond to the same average column height. A square
grid of side $d$ over the $z-r$ plane is used to create profiles, which are
averaged over the azimuth $\theta$ taking advantage of the cylindrical
symmetry. The averaged velocity and pressure for each bin in the grid is
calculated over the particles in the bin for each snapshot in the desired
stage of the discharge. To focus on a particular position in the silo we take
slices (usually horizontal slices) of the grid.

##  3 Results

###  3.1 Flow rate and bottom pressure

In Fig. 1(a), we show the particle flow rate as a function of column height
for a free discharging silo along with forced flows using different
overweights. As we can see, in the initial stages of a forced discharge, the
flow rate is the same as the free flow rate. However, after this initial
steady state, an accelerated flow is observed for all forced discharges. The
heavier the overweight, the sooner the acceleration phase starts and the
faster is the growth of the flow rate. This is consistent with the
experimental results shown in Ref. [18]. The inset to Fig. 1 shows that the
column height $h^{\prime}$, at which the accelerated flow starts, grows
logarithmically with the overweight $W$. Currently, we can not provide a
plausible explanation for this. As we will see in the next section, despite
observing the same flow rate during the initial phase of the discharge, the
forced flows display some interesting subtle differences when compared against
unforced discharges.

The pressure at the bottom of the silo during free and forced discharges is
shown in Fig. 1(b). While the pressure drops quickly at the end of the
discharge in an unforced flow, it rises for the forced flows. There seems to
be an apparent direct relation between bottom pressure and the flow rate.
However, this is not the case. The same particle flow rate can be observed for
very different bottom pressures by simply using denser materials and/or wider
silos [18; 20]. Also, the bottom pressure increases linearly with gravity, yet
the flow rate increases with $g^{0.5}$ [21; 22]. A discussion on the relation
between pressure, flow rate and dissipated power can be found in Ref. [18]. In
this paper we focus only on velocity profiles and leave the discussion on
pressure profiles for a future work.

###  3.2 Velocity profiles

Figure 4: Vertical velocity $v_{z}(r)$ at various heights $z_{\rm view}$ (as
indicated in Fig. 2) for the free discharge (left column) and for the forced
discharge with an overweight of $W=4W_{\rm D}$ (right column). The different
curves represent different column heights $h_{\rm fill}$ during the discharge
(see legend). Figure 5: Radial velocity profiles $v_{r}(r)$ at various
observatin planes $z_{\rm view}$ (as indicated in Fig. 2) for the free
discharge (left column) and for the forced discharge with an overweight of
$W=20W_{\rm D}$ (right column). The different curves represent different
column height $h_{\rm fill}$ during the discharge (see legend).

In Fig. 1, we have indicated four different column heights $h_{\rm fill}$
during the discharge (see vertical lines) where we have focused our attention.
We compare velocity profiles for different discharges at these different
points by ensuring that the granular column has a similar number of grains
inside the silo. The corresponding vertical velocity heat maps, $v_{z}(r,z)$,
are shown in Fig. 2 for a free discharge and for a forced discharge with the
heaviest overweight studied. For the free discharge, we observe the usual
overall features described in the literature: (a) there exists a stagnant zone
at the base surrounding the orifice ($v_{z}(r>D/2,z<\alpha r)\approx 0$, with
$\alpha$ a constant), (b) there is a focused high velocity region at and above
the orifice ($r<D/2,\,z<L\approx D/2$), (c) the free surface of the granular
column develops a depression at the center, and (d) the velocity is higher at
the central axis of the silo than at the walls ($v_{z}(r=0)>v_{z}(r=D_{\rm
s}/2)$). Some of these features are hard to see in the scale used in Fig. 2.
The main contrasts shown by the forced discharge are: (a) the stagnant zone is
shallower ($\alpha_{\rm forced}<\alpha_{\rm free}$), (b) the high velocity
region above the orifice is lower in height ($L_{\rm forced}<L_{\rm free}$),
and (c) the overweight forces a flat top surface of the granular column. Of
course, we also see the overall increase of the velocities at the final stages
where the flow increases as shown in Fig. 1(a).

To enhance the contrast between the forced and unforced velocity profiles, we
have plotted in Fig. 3 horizontal sections of the profiles (i.e., $v_{z}(r)$)
at different heights $z_{\rm view}=d/2$, $D/2$, $D_{\rm s}/2$ and $D_{\rm s}$
in the silo and for the four column heights $h_{\rm fill}$ considered during
the discharge. We have indicated these sections as horizontal lines in Fig. 2.
Moreover, the velocities have been scaled at each point during the discharge
(each column) by the velocity at the center of the orifice (notice that for
forced flows this velocity increases during discharge).

If we focus on the initial stage of the discharge (left column in Fig. 3), the
scaled velocity profiles at all heights $z_{\rm view}$ and for all the
overweights coincide. Actually, in this initial stage of the discharge even
the unscaled profiles match. At $z_{\rm view}=D_{\rm s}$ (top row), $v_{z}(r)$
is rather flat, with a slightly lower velocity next to the walls. However,
further down into the granular column the profile becomes steeper. Finally,
next to the plane of the base ($z_{\rm view}=d/2$) $v_{z}$ drops to zero
everywhere except at the orifice where the velocity displays a circular
profile consistent with Refs. [23; 24].

Figure 3 shows that, when the flow rate increases for the forced discharges
(two rightmost columns), the velocity profile displays some differences with
the free discharge. The most evident feature is an increase in the velocity at
the orifice (this can be appreciated in the unsacaled profiles of the inset,
bottom–right). However, the shape of the profile when scaled is conserved at
the aperture. The flat profile at $z_{\rm view}=D_{\rm s}$ also remains flat
upon acceleration. Nevertheless, the region $D/2<z<D_{\rm s}/2$ presents
nonlinear changes in the profile. In general, the scaled profile becomes less
steep as the overweight is heavier, reducing $v_{z}$ at $r=0$ and increasing
its value at $r=D_{\rm s}/2$.

In Fig. 4, we show some profiles from Fig. 3 but comparing in each plot
different points during the discharge for two forcing condition ($W=0$ and
$W=4W_{\rm D}$). A peculiar feature emerges in these plots. Whereas the
velocity profile for the unforced discharge remains unaltered during discharge
at the orifice and at a high plane ($z_{\rm view}=D_{\rm s}$), it does evolve
in the “transition region” $D/2<z<D_{\rm s}/2$. In this region, $v_{z}(r=0)$
increases (and $v_{z}(r=D_{\rm s}/2)$ decreases) as the silo discharges. This
is somewhat unexpected since the flow rate is steady and one may assume that
the internal velocity profiles are steady too. It is worth mentioning that
previous experimental studies have pointed out this velocity drift of the
“plug zone” [25; 26]. Interestingly, for forced flows, in the transition
region $D/2<z<D_{\rm s}/2$, the profile $v_{z}(r)$ does remain unaltered
during discharge until the start of the accelerated phase of the flow. This is
a remarkable feature and implies that one could homogenize the velocity
profile in a silo by using an overweight. Of course, in the final stages of
the discharge this would cause an increase of the flow rate.

Some profiles for the radial velocity in the silo are shown in Fig. 5. The
values of $v_{r}$ are at least one order of magnitude lower than those of
$v_{z}$. In all cases, the radial velocity is zero both at the walls
($v_{r}(r=D_{\rm s}/2)=0$) and at the axis of the silo ($v_{r}(r=0)=0$). A
maximum in $v_{r}$ is always found at an intermediate value of $r$. In
particular, for $z_{\rm view}=d$ the maximum occurs at $r=D/2$ as expected.
Once again, a forced flow yields profiles at all heights that are steady and
do not change much with time until the accelerated phase develops. However,
the unforced discharge displays increasing radial velocities at $z_{\rm
view}=D_{\rm s}/2$, while radial velocities drop during discharge at $z_{\rm
view}=D/2$ and $z_{\rm view}=d$. One interesting feature is that for the
forced flow, at $z_{\rm view}=D_{\rm s}/2$, the radial velocity decreases
significantly during he accelerated phase. Beyond this, overall, the radial
velocity is not affected by the fact that the forcing induces an acceleration
in the flow rate.

##  4 Conclusions

We have shown that the velocity profiles during the discharge of a silo can be
affected in a non trivial way by the forcing of the flow via an overweight.
Since the flow rate increases during the discharge due to forcing, the
profiles display larger values in the vertical velocities. However, the radial
velocities seem to be little affected.

When the vertical velocity profiles are scaled by the maximum velocity at the
orifice, one can consider changes in the shape of the profiles. We observed
that the profiles far from the orifice (one silo diameter above the base, or
four orifice diameters above the base) remain flat as in a free discharge.
Likewise, the scaled profile at the plane of the orifice conserves the shape
of the one observed for a free discharge. However, at a plane one orifice
radius above the base, the vertical velocity profile becomes flatter as the
overweight is increased. These results suggest that the use of an overweight
helps to develop a mass flow rate profile even for these flat-bottomed silos,
which may be of particular interest in the industry.

A number of open questions remain with respect to forced flows, such as: (i)
Is there a simple way to upgrade the Beverloo rule to a height-dependent
expression that takes into account the effect of an overweight? (ii) Is the
5/2 power in the Beverloo rule still valid? (iii) Since the acceleration of
the flow rate depends on the material, what material properties are more
relevant? (iv) Is the pressure profile inside the silo dramatically different
from the unforced discharge? (v) What is the undelying mechanism that induce
the accelerated phase to start logarithmically sooner as the overweight
increases? (vi) Are there connections with related experiments where an
overweight has induced drastic changes in the granular dynamics [27]? These,
and other questions, need to be addressed. The new knowledge that we earn
regarding forced discharges may help develop new models to understand even the
apparently simpler case of a free discharge.

Acknowledgments We thank J. R. Darias for valuable discussions. This work has
been supported by ANPCyT (Argentina) through grant PICT 2012-2155 and UTN
(Argentina) through grant PID MAUTNLP-2184.

## References

  * [1] Kadanoff, L.P.: Built upon sand: Theoretical ideas inspired by granular flows. Rev. Mod. Phys. 71, 435 (1999)
  * [2] de Gennes, P.G.: Granular matter: A tentative view. Rev. Mod. Phys. 71, S374 (1999)
  * [3] Jaeger, H.M., Nagel, S.R., Behringer, R.P.: Granular solids, liquids, and gases. Rev. Mod. Phys. 68, 1259 (1996)
  * [4] Duran, J.: Sands, Powders and Grains. Springer, New York (2000)
  * [5] Tighe, B.P., Sperl, M.: Pressure and motion of dry sand: Translation of Hagen’s paper from 1852. Gran. Matt. 9, 141 (2007)
  * [6] Beverloo, W.A., Leninger, H.A., van de Valde, J.: The flow rate of granular materials through an orifice. Chem. Eng. Sci. 15, 260 (1961)
  * [7] Nedderman, R.M.: Statics and kinematics of granular material. Cambridge University Press, New York (1992)
  * [8] Janssen, H.A.: Versuche uber getreidedruck in silozellen. Zeitschr. d. Vereines deutscher Ingenieure 39, 1045 (1895)
  * [9] Sperl, M.: Experiments on corn pressure in silo cells–translation and comment of Janssen’s paper from 1895. Gran. Matt. 8, 59 (2006)
  * [10] Aguirre, M.A., Grande, J.G., Calvo, A., Pugnaloni, L.A., Géminard, J.-C.: Pressure independence of granular flow through an aperture. Phys. Rev. Lett. 104, 238002 (2010)
  * [11] Wang, Y., Lu, Y., Ooi, J.Y.: A numerical study of wall pressure and granular flow in a flat-bottomed silo. Powder Tech. 282, 43 (2015)
  * [12] Perge, C., Aguirre, M.A., Gago, P.A., Pugnaloni, L.A., Le Tourneau, D., Géminard, J.-C.: Evolution of pressure profiles during the discharge of a silo. Phys. Rev. E 85, 021303 (2012)
  * [13] Walters, J.K.: A theoretical analysis of stresses in silos with vertical walls. Chem. Eng. Sci. 28, 13 (1973)
  * [14] Walters, J.K.: A theoretical analysis of stresses in axially-symmetric hoppers and bunkers. Chem. Eng. Sci. 28, 779 (1973)
  * [15] Walker, D.M.: An approximate theory for pressures and arching in hoppers. Chem. Eng. Sci. 21, 975 (1966).
  * [16] Walker, D.M., Blanchard, M.H.: Pressures in experimental coal hoppers. Chem. Eng. Sci. 22, 1713 (1967)
  * [17] Linford, A.: Flow Measurement & Meters. (2nd ed.). London: E. & F. N. Spon (1961)
  * [18] Madrid, M.A., Darias, J.R., Pugnaloni, L.A.: Forced flow of granular media: Breakdown of the Beverloo scaling. Europhys. Lett. 123, 14004 (2018)
  * [19] Kloss, C., Goniva, C., Hager, A., Amberger, S., Pirker, S.: Models, algorithms and validation for opensource DEM and CFD-DEM. Prog. Comput. Fluid Dynamics 12, 140 (2012)
  * [20] Staron, L., Lagrée, P.-Y., Popinet, S.: The granular silo as a continuum plastic flow: The hour-glass vs the clepsydra. Phys. Fluids 24, 103301 (2012)
  * [21] Dorbolo, S., et al.: Influence of the gravity on the discharge of a silo. Granular Matter 15, 263 (2013)
  * [22] Arévalo, R., Zuriguel, I., Maza, D., Garcimartín, A.: Role of driving force on the clogging of inert particles in a bottleneck. Phys. Rev. E 89, 042205 (2014)
  * [23] Janda, A., Zuriguel, I., Maza, D.: Flow rate of particles through apertures obtained from self-similar density and velocity profiles. Phys. Rev. Lett. 108, 248001 (2012)
  * [24] Rubio-Largo, S.M., Janda, A., Maza, D., Zuriguel, I, Hidalgo, R.C.: Disentangling the free-fall arch paradox in silo discharge. Phys. Rev. Lett. 114, 238002 (2015)
  * [25] Sielamowicz, I., Blonski, S., Kowalewski, T.A.: Optical technique DPIV in measurements of granular material flows, Part 1 of 3—plane hoppers. Chem. Eng. Sci. 60, 589 (2005)
  * [26] Waters, A.J., Drescher, A.: Modeling plug flow in bins/hoppers. Powder Tech. 113, 168 (2000)
  * [27] Metcalfe, G., Tennakoon, S. G. K., Kondic, L., Schaeffer, D. G., Behringer, R. P.: Granular friction, Coulomb failure, and the fluid-solid transition for horizontally shaken granular materials. Phys. Rev. E, 65, 031302 (2002).