# Stochastic Distance in Property Testing

Uri Meir Tel-Aviv University, Israel. Email<EMAIL_ADDRESS>Gregory
Schwartzman JAIST, Japan. Email<EMAIL_ADDRESS>Yuichi Yoshida NII, Japan.
Email<EMAIL_ADDRESS>
###### Abstract

We introduce a novel concept termed ”stochastic distance” for property
testing. Diverging from the traditional definition of distance, where a
distance $t$ implies that there exist $t$ edges that can be added to ensure a
graph possesses a certain property (such as $k$-edge-connectivity), our new
notion implies that there is a _high probability_ that adding $t$ _random_
edges will endow the graph with the desired property. While formulating
testers based on this new distance proves challenging in a sequential
environment, it is much easier in a distributed setting. Taking $k$-edge-
connectivity as a case study, we design ultra-fast testing algorithms in the
CONGEST model. Our introduction of stochastic distance offers a more natural
fit for the distributed setting, providing a promising avenue for future
research in emerging models of computation.

##  1 Introduction

Property testing has become a major focus in computational research over the
years. One of the main goals in this field is to quickly determine if a given
structure has a specific property or is far from having it. Traditionally,
this ”distance” from a property has been defined using the Hamming distance,
which counts the number of changes needed to give the structure the desired
property. But a question arises: Is this the best way to measure distance in
all situations, especially in emerging models of computation?

Consider the following motivating example. Distributed dynamic systems, such
as peer-to-peer networks, frequently experience changes in their structure as
nodes (clients) join or depart and edges may experience failures. For the sake
of resilience against failures, it is imperative for these systems to maintain
a topology with certain advantageous features, like $k$-edge-
connectivity111Going forward we simply write $k$-connectivity.. However,
maintaining this throughout the evolution of the network may require resource-
intensive corrections, which ideally should be minimized. Still, it might be
the case that some topologies are ”easy” to correct, in the sense that simply
adding a small number of random edges to the graph will make the network
topology $k$-connected. This can be seen as a ”low-cost” fixing operation,
compared to executing an elaborate algorithm that guarantees $k$-connectivity
for _every_ topology. A question arises: can we detect these easy-to-fix
topologies _fast_?

We take a first step in addressing the above and introduce a new distance
measure which we call _stochastic distance_. That is, we say that a graph
$G=(V,E)$ is $t$-stochastically-close to a property $\mathcal{P}$ if it holds
with high probability (w.h.p)222With probability at least $1-n^{-c}$ for some
constant $c>1$. The choice of $c$ does not affect the asymptotics of our
results. that adding (roughly) $t$ random edges to $G$ will make it have
property $\mathcal{P}$. Intuitively, the Hamming distance metric can be seen
as asking whether the input graph is close to _at least one_ graph instance
that has a desired property, while our new distance measure asks whether the
graph is close to _many instances_ that have the property.

To exemplify the usefulness of our new distance measure, we take the property
of $k$-connectivity as a case study. This is an extremely desirable graph
property in the distributed setting, as it guarantees that the system remains
connected even under several edge failures. In Section 3 we note that the
simple case of connectivity already becomes hard to test in the sequential
setting. However, using the distributed power of the system we can design
extremely fast distributed testers for both connectivity and $k$-connectivity.

###  1.1 Our model and results

In the distributed setting, a network of nodes, which is represented by a
communication graph $G=(V,E)$, aims to solve some graph problem with respect
to $G$. Every node in $G$ has unique ID of $O(\log n)$ bits. Computation
proceeds in synchronous rounds, in each of which every vertex can send a
message to each of its neighbors. The running time of the algorithm is
measured as the number of communication rounds it takes to finish. Our results
hold for the CONGEST model of distributed computation, where messages are
limited to $O(\log n)$ bits (where $n=|V|$).

A distributed 1-sided tester [CFSV19] for a property $\mathcal{P}$ (or simply
a tester) has the following guarantee. If the graph $G$ has the property, then
all nodes accept. If the graph is $\epsilon$-far from having the property,
then with probability larger than 2/3 _at least_ one node rejects. This
definition remains the same for both the Hamming distance metric and our
stochastic distance measure.

Note that $\epsilon\in(0,1)$ indicates the distance from the property relative
to the number of edges in the graph (i.e., $\epsilon|E|$ in the general model)
or to the possible number of edges in the graph (i.e., $\epsilon\binom{n}{2}$
in the dense model). In our model every non-edge is added with probability
$t/(\binom{n}{2}-|E|)$ (see Section 2 for an exact definition), therefore it
is more natural to use $t\in\mathbb{N}$ as the distance parameter rather than
$\epsilon$. That is, our testers decide whether the graph has a certain
property or if it is $t$-far from it. We state and prove the following two
theorems333Where $\tilde{O}$ subsumes factors logarithmic in $n$.:

######  Theorem 1.1.

There exists a deterministic algorithm in the CONGEST model, that for a
parameter $s\in\mathbb{N}$ runs in $O(s)$ rounds and distinguishes whether the
graph $G$ is connected, or is $\Omega((n\log n)/s)$-stochastically-far.

######  Theorem 1.2.

There exists a randomized algorithm in the CONGEST model, that for a parameter
$s\in\mathbb{N}$ runs in $\tilde{O}(s^{4})$ rounds and distinguishes w.h.p
whether the graph $G$ is $k$-connected, or is $\Omega((kn\log
n)/s)$-stochastically-far from being one.

Intuitively, the above states that the more random edges are added the easier
it is to check if the graph will become $k$-connected or not. That is, if
$s\approx kn\log n$ then checking whether a constant number of random edges
will make the graph $k$-connected is as hard as checking if the graph is
connected, which requires traversing the entire graph. If $s=O(1)$, then so
many edges are added that the graph almost surely becomes $k$-connected. Our
results provide a smooth transition between these two cases.

#### Related work

In (non-distributed) property testing, the objective is to devise algorithms
that can distinguish between graphs satisfying a property $\mathcal{P}$ and
graphs that are $\epsilon$-far from having the property with a high
probability. Testing connectivity properties in the bounded-degree model,
where we have query access to the input graph via a list of incidence lists,
has been extensively studied, including $k$-connectivity [GR02, YI10, Ore10],
$k$-vertex-connectivity [YI12, Ore10], $(k,l)$-sparsity [ITY12] and
supermodular-cut conditions [TY15].

The first distributed property testing algorithm was due to [BP11]. A thorough
study of distributed property testing was initiated in [CFSV19]. This was
followed by a long line of work, presenting new and improved testers for
various properties [AMPV22, EFF+17, FRST16, FHN20, LMR21, FV18]. All of these
works consider the Hamming distance handed down from the sequential testing
model.

$k$-connectivity received a large amount of attention in the distributed
literature [Thu97, CD20, DG23, Dor18, DHNS19, Par19, BEG+22]. There is a large
body of work that aims to find _sparse connectivity certificates_ – for a
$k$-connected graph the goal is to find a $k$-connected subgraph that has
$O(kn)$ edges. Another related problem is computing a $k$-edge-connected
spanning subgraph ($k$-ECSS) – for a $k$-connected graph the goal is to find
the _sparsest possible_ $k$-connected subgraph. We note that both these
problems assume that the input graph is $k$-connected, and are therefore
inherently different than the problem we consider.

##  2 Preliminaries

#### Distance from a property

We identify simple graphs $G=(V=[n],E)$ with the $\binom{n}{2}$-dimensional
characteristic vector of their edge set $E\subseteq\binom{V}{2}$, and use the
Hamming metric over these vectors, defined by
${d_{{\textnormal{\sf{HAM}}}}}(G,G^{\prime})=\mathopen{}\mathclose{{}\left|{\\{i\in\binom{V}{2}{\
:\ }G(i)\neq G^{\prime}(i)\\}}}\right|$, where $G(i)$ is the $i^{th}$ entry in
the vector $G$.

By extension, the distance of a graph $G$ from a family of graphs
$\mathcal{G}$ is:

${d_{{\textnormal{\sf{HAM}}}}}(G,\mathcal{G})=\min_{G^{\prime}\in\mathcal{G}}{d_{{\textnormal{\sf{HAM}}}}}(G,G^{\prime}).$

A property $\mathcal{P}$ is formally a family of graphs (e.g., all connected
graphs). Given positive integers $n$ and $t$, we define the YES case of the
corresponding testing problem to be all graphs $G=(V,E)$ in $\mathcal{P}$ over
$n$ vertices:

${\textnormal{\sf{YES}}}:=\\{G\in\\{0,1\\}^{\binom{V}{2}}{\ :\
}G\in\mathcal{P}\\}$

We define the NO case, denoted ${\textnormal{\sf{NO}}}_{t}^{\prime}$, to be
all graphs $G=(V,E)$ over $n$ vertices with Hamming distance at least $t$ from
YES:

${\textnormal{\sf{NO}}}_{t}^{\prime}:=\\{G\in\\{0,1\\}^{\binom{V}{2}}{\ :\
}{d_{{\textnormal{\sf{HAM}}}}}(G,{\textnormal{\sf{YES}}})\geq t\\}$

Motivated by connectivity, in the following we only consider monotone non-
decreasing properties, for which it is easy to see that only additions count
towards the distance from the property (note that many properties in the
literature are monotone non-increasing instead. For these, one can replace
additions with deletions). Formally, if $\mathcal{P}$ is a monotone non-
decreasing property, and $G\notin\mathcal{P}$ is a graph that does not satisfy
it, then for any $H\in\mathcal{P}$ with
${d_{{\textnormal{\sf{HAM}}}}}(G,H)={d_{{\textnormal{\sf{HAM}}}}}(G,\mathcal{P})$,
we have $E_{G}\subseteq E_{H}$ (or alternatively,
${d_{{\textnormal{\sf{HAM}}}}}(G,H)=\mathopen{}\mathclose{{}\left|{\\{i\in\binom{V}{2}{\
:\ }G(i)=0\wedge H(i)=1\\}}}\right|$).

#### Stochastic distance

We define _stochastic closeness_ to a property as follows:

######  Definition 1 (Random addition of edges).

For a graph $G=(V,E)$, we choose a random subset $E^{\prime}$ of the edge set
$\bar{E}=\binom{V}{2}\setminus E$, by adding each edge with probability
$t/\mathopen{}\mathclose{{}\left|{\bar{E}}}\right|$ independently, for
parameter
$t\in\mathopen{}\mathclose{{}\left[0,\mathopen{}\mathclose{{}\left|{\bar{E}}}\right|}\right]$.
We define the random graph $\mathrm{Add}(G,t):=(V,E\cup E^{\prime})$. We say
that $G^{\prime}=\mathrm{Add}(G,t)$ is created from $G$ by a _random addition
of edges_ with parameter $t$.

The parameter $t$ should be understood intuitively as the (expected) number of
random edges required to make the graph have the property $\mathcal{P}$ w.h.p.
Per our motivation, and in accordance with previous results for testing
connectivity, we allow ourselves the mild assumption that
$\mathopen{}\mathclose{{}\left|{\bar{E}}}\right|=\Omega(n^{2})$ which clearly
holds for any input relevant to our setting. The amount of edges we aim to
add, however, is always significantly smaller, $t=o(n^{2})$. In particular it
is always the case that
$t\leq\mathopen{}\mathclose{{}\left|{\bar{E}}}\right|$, as desired.

######  Definition 2 (Stochastic closeness to a monotone property).

For a monotone property $\mathcal{P}$, a graph $G\notin\mathcal{P}$ over $n$
vertices is said to be $t$-stochastically-close to satisfying $\mathcal{P}$ if
the graph $G^{\prime}=\mathrm{Add}(G,t)$ satisfies

$\Pr[G^{\prime}\notin\mathcal{P}]\leq n^{-c}$

for some global constant $c>1$. As shown in Appendix A, the constant $c$ can
be chosen arbitrarily without affecting stochastic closeness by more than a
constant factor.

We are now able to define the alternative set of NO instances:

${\textnormal{\sf{NO}}}_{t}:=\\{G\in\\{0,1\\}^{\binom{V}{2}}{\ :\
}G\notin{\textnormal{\sf{YES}}}\text{ and $G$ is not $t$-stochastically-close
to $\mathcal{P}$}\\}$

In this text our main focus is solving promise problems of type
$({\textnormal{\sf{YES}}},{\textnormal{\sf{NO}}}_{t})$, rather than
$({\textnormal{\sf{YES}}},{\textnormal{\sf{NO}}}_{t}^{\prime})$.

#### Comparing the two notions of distance.

As an illustrative example, consider two $n$-node graphs, both with exactly
two connected components: in $G_{1}$ a constant-size component is disconnected
from the rest of the graph, while in $G_{2}$ there are two components of the
same size, $n/2$. While both graphs are exactly one edge away from being
connected (i.e, both have hamming distance $1$). The situation is quite
different if edges are added randomly, instead of being handpicked, leading to
different _stochastic_ distance. While a small number of edges ($\sim\log n$)
are already likely to connect $G_{2}$, the same amount has only probability
$o(1)$ to connect $G_{1}$.

##  3 Warm-up: Connectivity with Stochastic Distance

In this section we deal with the graph connectivity property for a network
that is not necessarily connected. This section aims to present the ideas used
in the following section about $k$-connectivity. We use the following
terminology: when a graph is disconnected, write $G=\bigcup_{i=1}^{m}C_{i}$ as
the unique decomposition of $G$ into its connected components
$C_{1},\dots,C_{m}$, with $C_{i}=(V_{i},E_{i})$, and
$s_{i}:=\mathopen{}\mathclose{{}\left|{V_{i}}}\right|$ for their sizes.

We make the following observation:

######  Observation.

Let $G=\bigcup_{i=1}^{m}C_{i}$ be a disconnected graph (i.e., $m\geq 2$), and
let $s=\frac{1}{m}\sum_{i\in[m]}s_{i}$, then $G$ is $O(\frac{n}{s})$-close to
being connected in Hamming distance.

Indeed, it holds that $s=\frac{1}{m}\sum_{i\in[m]}s_{i}=n/m$, which means that
$m=n/s$. As a single edge can be used to connect two components, adding
$m-1=n/s-1$ edges suffices to connect the graph.

The observation is also tight: there exist graphs that require exactly this
number of additions. Joined with a Markovian argument, one can deduce that for
any graph that is far from connectivity, there exists _many_ small connected
components. This is a key argument in the analysis of existing connectivity
testers (using Hamming distance) [GR02].

The main part of this section deals with proving a statement of similar taste
for stochastic distance. While the Hamming distance of a graph from being
connected is dictated by the _average_ size of a connected component, for
stochastic distance this is dictated by the _minimum_ size of a connected
component. As a result, a graph that is far from being connected in stochastic
distance is only guaranteed to have _one_ small connected component. Formally,
we prove the following lemma:

######  Lemma 3.1.

Let $G=\bigcup_{i=1}^{m}C_{i}$ be a disconnected graph (that is, $m\geq 2$),
with components of sizes
$s_{i}=\mathopen{}\mathclose{{}\left|{V_{i}}}\right|$. Then $G$ is
$O\mathopen{}\mathclose{{}\left((n\log n)/s}\right)$-stochastically-close to
being connected, where $s=\min_{i\in[m]}\\{s_{i}\\}$.

###### Proof.

Recall that when considering stochastic distance every non-edge is added with
some probability $p$. Consider the set of bad events
$\\{B_{k}\\}_{k=1}^{\lfloor{m/2}\rfloor}$, where $B_{k}$ is the event that
there exists a set of exactly $k$ connected components $C_{i_{1}},\dots
C_{i_{k}}$ such that none of the edges between $\bigcup_{j=1}^{k}C_{i_{j}}$
and the rest of the graph are added. The important observation is that the
graph stays disconnected if and only if one of these bad events occurs. We go
on to bound the probability of each of these bad events.

Fix $k$. Our goal is to bound $\Pr[B_{k}]$. There are $\binom{m}{k}$ ways to
choose a subset of $k$ components. Fix one such choice $i_{1},\dots i_{k}$ and
denote the set of vertices in these components by
$U=\bigcup_{j=1}^{k}V_{i_{j}}$. As each component is of size at least $s$, we
have $\mathopen{}\mathclose{{}\left|{U}}\right|\geq ks$, applying the same
reasoning to the remaining graph, made of the rest of the components:
$\mathopen{}\mathclose{{}\left|{V\setminus U}}\right|\geq(m-k)s\geq ks$ nodes
(the second inequality holds since $k\leq m/2$). Thus, we have
$ks\leq\mathopen{}\mathclose{{}\left|{U}}\right|\leq n-ks$, and consequently
we get:

$\mathopen{}\mathclose{{}\left|{U}}\right|\cdot\mathopen{}\mathclose{{}\left|{V\setminus
U}}\right|=\mathopen{}\mathclose{{}\left|{U}}\right|\cdot(n-\mathopen{}\mathclose{{}\left|{U}}\right|)\geq
ks(n-ks).$

where the inequality is true since $f(x)=x(n-x)$ is unimodal and symmetric on
the interval $[ks,n-ks]$. The probability of $U$ staying disconnected from
$V\setminus U$ is thus bounded by:

$(1-p)^{\mathopen{}\mathclose{{}\left|{U}}\right|(n-\mathopen{}\mathclose{{}\left|{U}}\right|)}\leq
e^{-p\mathopen{}\mathclose{{}\left|{U}}\right|(n-\mathopen{}\mathclose{{}\left|{U}}\right|)}\leq
e^{-pks(n-ks)}$

And by a union bound over all choices of $U$ with $k$ connected components, we
get:

$\Pr[B_{k}]\leq\binom{m}{k}e^{-pks(n-ks)}\leq e^{-pks(n-ks)+k\log m}\leq
e^{-pksn+p(ks)^{2}+k\log n}$

Thus, by taking $p=2(c+2)\log n/(sn)$, the expression in the exponent is
bounded by:

$-\frac{2(c+2)\log n\cdot ksn}{sn}+\frac{2(c+2)\log n(ks)^{2}}{sn}+k\log
n=(2(c+2)(ks/n-1)+1)k\log n\leq-(c+1)k\log n$

where the last inequality uses $ks/n\leq(m/2)s/n\leq 1/2$. This, in turn,
bounds the probability of the bad event by:

$\Pr[B_{k}]\leq e^{-(c+1)k\log
n}\leq\mathopen{}\mathclose{{}\left(\frac{1}{n}}\right)^{-(c+1)k}$

Union bounding over all values of $k$, we get

$\Pr\mathopen{}\mathclose{{}\left[\bigvee_{k=1}^{\lfloor{m/2}\rfloor}B_{k}}\right]\leq\sum_{k=1}^{\lfloor{m/2}\rfloor}n^{-(c+1)k}\leq\sum_{k=1}^{\infty}n^{-(c+1)k}\leq
2n^{-(c+1)}\leq n^{-c}$

where the second to last inequality uses the sum of an infinite geometric
series with $n^{-(c+1)}\leq 1/2$, and the last simply uses $n\geq 2$.

Finally, we get that $G$ is connected w.h.p. This implies that $G$ is
$t$-stochastically-close to being connected, with
$t=O\mathopen{}\mathclose{{}\left((n\log n)/s}\right)$ (recall that
$\mathopen{}\mathclose{{}\left|{\bar{E}}}\right|=\Omega(n^{2})$).

∎

#### Tightness of Lemma 3.1.

We focus on the smallest connected component, $V_{i}$ of size $s_{i}=s$. There
are at most $s(n-s)\leq sn$ potential edges to connect $V_{i}$ to the rest of
the graph. If we take $p^{\prime}=c\log n/(4sn)$, then the probability none of
them is added satisfies:

$(1-p^{\prime})^{s(n-s)}\geq(1-p^{\prime})^{sn}\geq
e^{-2p^{\prime}sn}=e^{-c\log n/2}=n^{-c/2}>n^{-c},$

where the second inequality uses $1-x\geq e^{-2x}$, which holds for
$x\in[0,1/2]$.

Using the counter-positive of Lemma 3.1, a graph $G$ that is $O((n\log
n)/s)$-stochastically-far from being connected is guaranteed to have a
connected component of size _at most_
$O\mathopen{}\mathclose{{}\left(s}\right)$. We state the following theorem.

See 1.1

###### Proof.

Assume that the parameter $s$ is known to all nodes in the network. Each node
runs a distributed DFS algorithm. Every execution is associated with an ID,
which is simply the ID of the root of the DFS tree. When multiple DFS
executions visit the same node, all execution are terminated, except that with
the maximum ID. When a DFS execution visits $s$ nodes, it terminates and
checks whether there is an outgoing edge from any visited node to any
unvisited node. If there is, then it accepts (i.e., the graph is connected),
otherwise it rejects (i.e., the graph is far from being connected).
Correctness follows from Lemma 3.1. It is clear that there is no congestion
and that the algorithm terminates in $O(s)$ iterations.

∎

##  4 Stochastic Distance from $k$-Connectivity

This section deals with $k$-connectivity, for any $k\geq 1$. We aim to
characterize stochastic distance of a graph in terms of cuts, focusing on a
specific parameter-of-interest denoted by $s_{k}(G)$: the smallest size of a
vertex set that has a cut strictly smaller than $k$. In terms of this
parameter, the following can be shown:

######  Theorem 4.1.

Let $G=(V,E)$ and $s=s_{k}(G)$, then $G$ is
$O\mathopen{}\mathclose{{}\left((k\cdot n\log n)/s}\right)$-stochastically-
close to being $k$-connected.

Similarly to Lemma 3.1, this theorem is tight, up to a factor of $k$. The rest
of this section deals with proving the above theorem. First the parameter
$s_{k}(G)$ is formally defined and discussed. Later, we generalize Lemma 3.1
to bound the number of random edge additions required to increase the
connectivity of a graph by one. In the last part we formally prove Theorem
4.1.

###  4.1 Properties of minimal cuts

For any vertex set, $U\subseteq V$, we write the cut size of $U$ as
$c(U):=\mathopen{}\mathclose{{}\left|{E(U,V\setminus U)}}\right|$. We use
$d(t):=t(n-t)$ for the _potential_ amount of edges between any $t$ vertices
and the rest of the graph, and for a specific vertex set, $U$, we slightly
abuse notation and write $d(U)=d(\mathopen{}\mathclose{{}\left|{U}}\right|)$.

For any parameter $k\in\mathbb{N}$ and graph $G=(V,E)$, we define the
collection of small cuts as the cuts that are strictly smaller than $k$:

$\mathcal{S}_{k}(G):=\\{U\subseteq V{\ :\ }c(U)<k\text{ and
}U\neq\emptyset\\}$

A value of interest for us will be the size of the smallest set in such a
collection. Formally we define:

$s_{k}(G):=\min_{U\in\mathcal{S}_{k}(G)}\mathopen{}\mathclose{{}\left|{U}}\right|$

When the connectivity parameter $k$ and the graph $G$ are clear from context,
we omit either one or both (writing $s_{k},s(G)$ or simply $s$ instead). If
the collection is empty for some $k$ and $G$, we define $s_{k}(G)=n$. Note
that $s_{k}(G)=n$ if and only if $G$ is indeed $k$-connected.

We show that $s_{k}(G)$ has certain monotonicity properties with respect to
the parameters $G$ and $k$. Indeed, by definition a larger value for $k$
creates a larger collection of cuts, i.e.,
$\mathcal{S}_{k}(G)\subseteq\mathcal{S}_{k+1}(G)$. On the other hand, adding
edges to the graph can only increase the cut of any given vertex set, $U$.
Thus, any $U$ with a small cut after additions, also had a small cut before
additions. Formally, if $G\subseteq G^{\prime}$ (i.e.,
$G=(V,E),G^{\prime}=(V,E^{\prime})$ and $E\subseteq E^{\prime}$), we have
$\mathcal{S}_{k}(G^{\prime})\subseteq\mathcal{S}_{k}(G)$. The minimum over
elements in a collection can only decrease if we add elements to the
collection, and hence we have:

######  Observation (Monotonicity of $s_{k}(G)$).

The parameter $s_{k}(G)$ is monotone non-increasing in $k$, and monotone non-
decreasing in $G$.

Below, we will be interested in finding the smallest vertex set $U$ in the
collection $\mathcal{S}_{k}(G)$. This element determines the value $s$. The
following proposition shows a property of such a set $U$ that will be useful
for the algorithm:

######  Proposition 4.2.

Fix $k\in\mathbb{N}$ and a graph $G=(V,E)$. For any subset $U\subseteq V$ with
a cut less than $k$ ($c(U)<k$) and of minimal size
($\mathopen{}\mathclose{{}\left|{U}}\right|=s_{k}$) the induced subgraph
$G[U]$ is connected.

###### Proof.

Assume otherwise, then we can break $G[U]$ into its connected components:
$U=\bigcup_{i}U_{i}$. Each such component has strictly less nodes than $U$.
Moreover, we have:

$\displaystyle c(U_{i})=E(U_{i},V\setminus U_{i})=E(U_{i},V\setminus U)\leq
E(U,V\setminus U)=c(U),$

where the second equality holds since there are no edges between different
components of $U$. We conclude that each $U_{i}$ has a cut of size at most
$c(U)<k$, but their size is strictly smaller than $s$, which leads to a
contradiction. ∎

###  4.2 Increasing the connectivity by one

Using the notations of this section, the statement of Lemma 3.1 is that any
graph that is “$0$-connected” (i.e., disconnected) is
$O\mathopen{}\mathclose{{}\left(n\log(n)/s_{1}}\right)$-stochastically-close
to being $1$-connected. This is true since $s_{1}$ is exactly the size of the
smallest connected component in $G$.

We generalize this statement for $k$-connectivity:

######  Lemma 4.3.

Any $(k-1)$-connected graph $G$ with $n\geq 4k$ nodes is
$O\mathopen{}\mathclose{{}\left(n\log(n)/s_{k}}\right)$-stochastically-close
to being $k$-connected.

###### Proof.

For $k=1$, the proof is complete due to Lemma 3.1. For $k>1$, let $G$ be a
$(k-1)$-connected graph. Thus, all minimum cuts have $k-1\geq 1$ edges ($G$ is
connected). We estimate the number of random edges needed to make all sets in
$\mathcal{S}_{k}(G)$ have a cut of size at least $k$.

We identify minimum cut with a partition of $V$ to $U$ and $V\setminus U$
(w.l.o.g, $\mathopen{}\mathclose{{}\left|{U}}\right|\leq\lfloor{n/2}\rfloor$).
As in Lemma 3.1 assume that every non-edge is added with probability $p$.
Consider the event $B_{U}$ that $U$ remains with cut of size $k-1$. That is,
not a single edge was added between $U$ and $V\setminus U$. There are exactly
$d(U)-(k-1)$ potential additions, and so:

${\Pr\mathopen{}\mathclose{{}\left[{B_{U}}}\right]}=(1-p)^{d(U)-(k-1)}=(1-p)^{\mathopen{}\mathclose{{}\left|{U}}\right|(n-\mathopen{}\mathclose{{}\left|{U}}\right|)-(k-1)}\leq(1-p)^{s_{k}\cdot
n/4}\leq e^{-s_{k}\cdot pn/4},$

where the first inequality uses
$n-\mathopen{}\mathclose{{}\left|{U}}\right|\geq n/2\ ,\
\mathopen{}\mathclose{{}\left|{U}}\right|\geq s_{k}(G)$ and
$k\leq\mathopen{}\mathclose{{}\left|{U}}\right|n/4$ to lower bound the
exponent.

By taking $p=4(c+2)\log n/(s_{k}n)$, this bound becomes

$e^{-s_{k}\cdot pn/4}=e^{-(c+2)\log n}=n^{-(c+2)}$

We finish the proof by using a union bound over all minimum cuts. There are at
most $\binom{n}{2}\leq n^{2}$ of them due to well known corollary of Karger’s
Algorithm [Kar93]. The probability that $G$ is not $k$-connected after the
edge additions is at most

$\sum_{U\in\mathcal{S}_{k}(G)}{\Pr\mathopen{}\mathclose{{}\left[{B_{U}}}\right]}\leq
n^{2}\cdot n^{-(c+2)}=n^{-c}.\qed$

###  4.3 Putting it all together

We are now ready to prove Theorem 4.1. Our proof considers an alternative
addition process which is easier to analyze. Intuitively, let
$p^{\prime}\approx p/k$ and consider the following process. “Repeat $k$ times:
add each edge to the graph independently with probability $p^{\prime}$”. We
formalize the above and bound the required value of $p^{\prime}$ for the
alternative process, analyzing each of the $k$ iterations separately with
Lemma 4.3. We finish up by relating the original addition processes to the
alternative one.

###### Proof of Theorem 4.1.

Denote by $r<k$ the connectivity of $G$ (if $G$ is disconnected, then $r=0$).
We consider $k-r$ (at most $k$) iterations of additions, which we enumerate by
$r+1,\dots,k$. We further denote by $G_{i}$ the graph after iteration $i$ (and
$G_{r}=G$).

First we consider process (A), where at each iteration
$i\in\\{r+1,\dots,k\\}$, each edge is independently added with probability

$p_{i}=4(c+3)n\log n/s_{i+1}(G_{i}).$

Applying Lemma 4.3 for each iteration $i$ we have the following: The
probability that $G_{i}$ is $i$-connected, _given that $G_{i-1}$ is
$(i-1)$-connected_ is at least $1-n^{-(c+1)}$. Union bounding over all
$k-r\leq n$ iterations, we have that with probability at least $1-n^{-c}$, the
final graph $G_{k}$ is $k$-connected.

Next, consider an adjusted process (B) that also works in iterations, but uses
a fixed value

$p^{\prime}=4(c+3)n\log n/s_{k}(G).$

Using the monotonicity of $s_{k}(G)$, we have

$s_{k}(G)=s_{k}(G_{r})\leq s_{i+1}(G_{r})\leq s_{i+1}(G_{i}),$

and thus $p_{i}\leq p^{\prime}$ for all values of $i$.

Let us focus on a single non-edge of $G$, call it $(u,v)$, and follow it
through the entire process. The probability $(u,v)$ is added to $G_{k}$ is
higher in process (B) than it is in process (A), since $p^{\prime}\geq p_{i}$
for all $i$. On the other hand, this probability is at most $p^{\prime}k$, by
a union bound over all iterations of process (B).

Lastly, consider process (C), a one-shot random addition, using

$p=p^{\prime}k=4(c+3)kn\log n/s_{k}(G).$

The probability of every non-edge being added in process (C) is higher than it
is in process (B) which is in turn higher than process (A). By monotonicity of
$k$-connectivity (as a graph property), the probability that $G_{k}$ is a
$k$-connected graph is therefore also higher in process (C) than it is in
process (A), and is therefore at least $1-n^{-c}$. ∎

The counter-positive of Theorem 4.1 means that any graph $G$ which is
$O\mathopen{}\mathclose{{}\left((k\cdot n\log n)/s}\right)$-stochastically-far
from being $k$-connected has a set $W$ of at most $s$ nodes with a cut smaller
than $k$. We call such set $W$ an $(s,k)$-_witness_ , or simply a _witness_
when $k$ and $s$ are clear from context.

##  5 Distributed algorithm for $k$-connectivity

In this section, we provide a distributed algorithm that detects an
$(s,k)$-witness within $O(s^{4}\log n)$ rounds in the CONGEST model w.h.p. We
state with the following useful lemma444The original lemma in [GR02] uses the
notion of a _$j$ -extreme_ node set which is equivalent to our notion of a
$(s,k$)-witness.:

######  Lemma 5.1 (Lemma 3.16 in [GR02]).

Let $W$ be an $(s,k)$-witness. Suppose that each edge in the graph is
independently assigned a uniformly distributed cost in $[0,1]$. Then, with
probability at least
$\Theta\mathopen{}\mathclose{{}\left(s^{-2(1-1/k)}}\right)$, $W$ contains a
spanning tree such that every edge in the tree has cost smaller than any edge
in the cut $E(W,V\setminus W)$.

Specifically, if the tree guaranteed by the above lemma exists, the MST must
also have the same guarantees. Furthermore, as all edge costs are unique
w.h.p., the MST is unique w.h.p. When referring to the above lemma, it will be
convenient to refer to a single tree, the MST induced by the cost function
(i.e., when referring to the spanning tree guaranteed by Lemma 5.1, we always
refer to an MST).

Given a starting vertex $w$ and a size bound $s$, consider the following
random process:

  * •

Input: start vertex $u\in V$, size bound $s\in\mathbb{N}$.

  * •

Assign uniformly random weights to all edges: $w:E\to[0,1]$.

  * •

Start with a singleton set $W=\\{u\\}$. As long as
$\mathopen{}\mathclose{{}\left|{W}}\right|<s$, repeat the following:

    * –

Choose the smallest cut edge $e=\mathrm{argmin}_{e\in E(W,V\setminus W)}w(e)$.

    * –

Update $W$ to include the new node of $e$ in $V\setminus W$.

    * –

If $c(W)<k$ then declare $W$ as an $(s,k)$-witness.

Lemma 5.1 implies that repeating the above procedure $\tilde{\Theta}(s^{2})$
times detects a witness w.h.p.

In [GR02] a small amount of random nodes is sampled, and the above procedure
is applied for each of them. This is possible since any graph that is far from
$k$-connectivity in _Hamming_ distance contains many witnesses. In our case, a
graph that is _stochastically_ far only guarantees a single witness, and
therefore it is costly to detect the witness in the standard (query) model. We
leverage the distributed nature of the system to apply the witness detection
procedure to all nodes in parallel.

#### Distributed implementation

The above algorithm admits a simple distributed implementation. First, we
assign random weights in $[0,1]$ to all edges in the graph, this guarantees
that with some small probability there exists a spanning tree within the
witness component satisfying the guarantees of Lemma 5.1. Assume this tree
exists and denote this tree by $T$. It will be clear from our algorithm that
if this tree does not exist, the running time does not change however we may
simply not detect the witness component if it exists.

Every node grows a cluster as follows. Every cluster can be implemented via a
tree rooted at a leader node. All nodes in the cluster know for each neighbor
whether it is in the cluster or not. To pick the next edge to be added to the
cluster the edge weights are propagated along the tree towards the root,
taking the minimum at every node. Finally, the root propagates the minimum
value to all nodes in the cluster and the corresponding edge is added to the
cluster. After each edge addition the cluster checks whether the current cut
size is smaller than $k$ and terminates if this is the case (a witness is
found). For ease of analysis let us define an _iteration_ as the step of
adding a single edge (and vertex) to the cluster. When running this procedure
from multiple nodes we can have every cluster wait for $\Theta(i)$ rounds to
complete the $i$-th iteration. This will guarantee when running this procedure
from multiple nodes that the iterations are executed in lock-step. We execute
this process for $s$ iterations. This results in a running time of $O(s^{2})$
rounds.

In order to detect a witness component, we must execute the above algorithm to
completion, starting from a node within the witness component. We do not know
which nodes are within the witness component before executing the algorithm,
and running the procedure to completion may cause congestion. To overcome
this, we execute the procedure from all nodes simultaneously, but prioritize
executions that overlap according to a priority condition.

The priority of the cluster at iteration $i$ is the largest edge cost that was
added to the cluster so far. Let us call this the _max-edge_ value. Whenever
multiple executions reach the same node, executions with higher max-edge
values are terminated (ties are broken via the cluster root IDs). As clusters
add edges greedily according to edge weights, we know that only edges from $T$
will be added to clusters whose execution starts from the witness component.
That is, all edges in $T$ will be added, at which point the small cut will be
detected and all nodes in the cluster will reject.

As we terminate executions that visit the same node, we never experience
congestion. It is sufficient to prove that at least one cluster execution that
starts within the witness component survives. As all edges in the tree have
weights smaller than the cut edges this means that the execution of clusters
that start within the witness component is not affected by clusters that start
from outside the component. This is because they always have a lower max-edge
value due to guarantees on the weights of $T$. Furthermore, in every iteration
at least one cluster in the witness component is not terminated. That is, the
cluster with highest priority inside the witness component at iteration $i$
must survive. We conclude that there exists a cluster construction that start
within the component and terminates within $O(s^{2})$ rounds. To get the
guarantee of Lemma 5.1 w.h.p., we must repeat the process $\tilde{O}(s^{2})$
times. Thus, the final running time is $\tilde{O}(s^{4})$. We state the
following theorem:

See 1.2

## References

  * [AMPV22] John Augustine, Anisur Rahaman Molla, Gopal Pandurangan, and Yadu Vasudev.  Byzantine connectivity testing in the congested clique.  In DISC, volume 246 of LIPIcs, pages 7:1–7:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
  * [BEG+22] Marcel Bezdrighin, Michael Elkin, Mohsen Ghaffari, Christoph Grunau, Bernhard Haeupler, Saeed Ilchi, and Václav Rozhon.  Deterministic distributed sparse and ultra-sparse spanners and connectivity certificates.  In SPAA, pages 1–10. ACM, 2022.
  * [BP11] Zvika Brakerski and Boaz Patt-Shamir.  Distributed discovery of large near-cliques.  Distributed Comput., 24(2):79–89, 2011.
  * [CD20] Keren Censor-Hillel and Michal Dory.  Fast distributed approximation for TAP and 2-edge-connectivity.  Distributed Comput., 33(2):145–168, 2020.
  * [CFSV19] Keren Censor-Hillel, Eldar Fischer, Gregory Schwartzman, and Yadu Vasudev.  Fast distributed algorithms for testing graph properties.  Distributed Comput., 32(1):41–57, 2019.
  * [DG23] Michal Dory and Mohsen Ghaffari.  A nearly time-optimal distributed approximation of minimum cost _k_ -edge-connected spanning subgraph.  In SODA, pages 4296–4334. SIAM, 2023.
  * [DHNS19] Mohit Daga, Monika Henzinger, Danupon Nanongkai, and Thatchaphol Saranurak.  Distributed edge connectivity in sublinear time.  In STOC, pages 343–354. ACM, 2019.
  * [Dor18] Michal Dory.  Distributed approximation of minimum k-edge-connected spanning subgraphs.  In PODC, pages 149–158. ACM, 2018.
  * [EFF+17] Guy Even, Orr Fischer, Pierre Fraigniaud, Tzlil Gonen, Reut Levi, Moti Medina, Pedro Montealegre, Dennis Olivetti, Rotem Oshman, Ivan Rapaport, and Ioan Todinca.  Three notes on distributed property testing.  In DISC, volume 91 of LIPIcs, pages 15:1–15:30. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
  * [FHN20] Pierre Fraigniaud, Magnús M. Halldórsson, and Alexandre Nolin.  Distributed testing of distance-k colorings.  In SIROCCO, volume 12156 of Lecture Notes in Computer Science, pages 275–290. Springer, 2020.
  * [FRST16] Pierre Fraigniaud, Ivan Rapaport, Ville Salo, and Ioan Todinca.  Distributed testing of excluded subgraphs.  In DISC, volume 9888 of Lecture Notes in Computer Science, pages 342–356. Springer, 2016.
  * [FV18] Hendrik Fichtenberger and Yadu Vasudev.  A two-sided error distributed property tester for conductance.  In MFCS, volume 117 of LIPIcs, pages 19:1–19:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.
  * [GR02] Oded Goldreich and Dana Ron.  Property testing in bounded degree graphs.  Algorithmica, 32(2):302–343, 2002.
  * [ITY12] Hiro Ito, Shin-Ichi Tanigawa, and Yuichi Yoshida.  Constant-time algorithms for sparsity matroids.  In International Colloquium on Automata, Languages, and Programming, pages 498–509. Springer, 2012.
  * [Kar93] David R. Karger.  Global min-cuts in rnc, and other ramifications of a simple min-cut algorithm.  In SODA, pages 21–30. ACM/SIAM, 1993.
  * [LMR21] Reut Levi, Moti Medina, and Dana Ron.  Property testing of planarity in the CONGEST model.  Distributed Comput., 34(1):15–32, 2021.
  * [Ore10] Y Orenstein.  Testing properties of directed graphs.  Master’s thesis, School of Electrical Engineering, 2010.
  * [Par19] Merav Parter.  Small cuts and connectivity certificates: A fault tolerant approach.  In DISC, volume 146 of LIPIcs, pages 30:1–30:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * [Thu97] Ramakrishna Thurimella.  Sub-linear distributed algorithms for sparse certificates and biconnected components.  J. Algorithms, 23(1):160–179, 1997.
  * [TY15] Shin-Ichi Tanigawa and Yuichi Yoshida.  Testing the supermodular-cut condition.  Algorithmica, 71(4):1065–1075, 2015.
  * [YI10] Yuichi Yoshida and Hiro Ito.  Testing $k$-edge-connectivity of digraphs.  Journal of systems science and complexity, 23:91–101, 2010.
  * [YI12] Yuichi Yoshida and Hiro Ito.  Property testing on $k$-vertex-connectivity of graphs.  Algorithmica, 62(3-4):701–712, 2012.

##  Appendix A Robustness of Stochastic Closeness

The following claim is used to show robustness of stochastic closeness
(Definition 2) with respect to the choice of the global constant $c$.
Intuitively speaking, by repeating the random addition only a constant number
of times, the probability of not attaining the property $\mathcal{P}$ can be
reduced to any small polynomial.

######  Claim.

Fix a monotone property $\mathcal{P}$, a graph $G\notin\mathcal{P}$ over $n$
vertices, and constant $c>1$. If for some
$t\in\mathopen{}\mathclose{{}\left[0,\mathopen{}\mathclose{{}\left|{\bar{E}}}\right|}\right]$,
it holds that

$\Pr[\mathrm{Add}(G,t)\notin\mathcal{P}]\leq n^{-c},$

then for any $m\in\mathbb{N}$ such that
$mt\in\mathopen{}\mathclose{{}\left[0,\mathopen{}\mathclose{{}\left|{\bar{E}}}\right|}\right]$,
it holds that

$\Pr[\mathrm{Add}(G,mt)\notin\mathcal{P}]\leq n^{-mc}.$

###### Proof.

Recall that in the randomly augmented graph $\mathrm{Add}(G,t)$ each edge
$e\in\bar{E}$ is added independently with probability $t/|\bar{E}|$. Let
$G_{1},\dots,G_{m}$ be $m$ independent copies of $\mathrm{Add}(G,t)$. By
definition, we have

$\Pr\mathopen{}\mathclose{{}\left[\bigwedge_{i=1}^{m}\
G_{i}\notin\mathcal{P}}\right]=\prod_{i=1}^{m}\Pr\mathopen{}\mathclose{{}\left[G_{i}\notin\mathcal{P}}\right]\leq
n^{-mc}.$

Define $G^{\prime}=\bigcup_{i=1}^{m}G_{i}$, the union of all $m$ randomly
augmented graphs. $G^{\prime}$ trivially contains all edges of $G$. On the one
hand, the probability that each edge $e\in\bar{E}$ appears in $G^{\prime}$ is
at most $(mt)/|\bar{E}|$, by a union bound over the $m$ attempts to add it.
Since the property $\mathcal{P}$ is monotone, we have

$\Pr\mathopen{}\mathclose{{}\left[Add(G,mt)\notin\mathcal{P}}\right]\leq\Pr\mathopen{}\mathclose{{}\left[G^{\prime}\notin\mathcal{P}}\right].$

On the other hand, $G^{\prime}$ is a supergraph of $G_{i}$ for all $i\in[m]$.
Using again the monotonicity of $\mathcal{P}$, we can write

$\Pr\mathopen{}\mathclose{{}\left[G^{\prime}\notin\mathcal{P}}\right]=\Pr\mathopen{}\mathclose{{}\left[\bigwedge_{i=1}^{m}\
G^{\prime}\notin\mathcal{P}}\right]\leq\Pr\mathopen{}\mathclose{{}\left[\bigwedge_{i=1}^{m}\
G_{i}\notin\mathcal{P}}\right]\leq n^{-mc},$

which concludes the proof. ∎


# Fight Virus Like a Virus: A New Defense Method Against File-Encrypting
Ransomware

Joshua Morris  University of Missouri, Columbia, MO  Dan Lin  University of
Missouri, Columbia, MO  Marcellus Smith  Auburn University, Auburn, AL

###### Abstract

Nowadays ransomware has become a new profitable form of attack. This type of
malware acts as a form of extortion which encrypts the files in a victim’s
computer and forces the victim to pay the ransom to have the data recovered.
Even companies and tech savvy people must use extensive resources to maintain
backups for recovery or else they will lose valuable data, not mentioning
average users. Unfortunately, not any recovery tool can effectively defend
various types of ransomware. To address this challenge, we propose a novel
ransomware defense mechanism that can be easily deployed in modern Windows
system to recover the data and mitigate a ransomware attack. The uniqueness of
our approach is to fight the virus like a virus. We leverage Alternative Data
Streams which are sometimes used by malicious applications, to develop a data
protection method that misleads the ransomware to attack only file ’shells’
instead of the actual file content. We evaluated different file encrypting
ransomware and demonstrate usability, efficiency and effectiveness of our
approach.

Keywords: ADS (Alternative Data Streams), Ransomware, File encryption

##  I Introduction

Ransomware is a type of malware that has quickly become a rife means of attack
due to the large monetary gains that are achievable. Specifically, ransomware
operates by exploiting an attack vector such as a fake Adobe Acrobat update or
a malicious email attachment to deliver a payload to a victim’s computer
system. Once this payload is executed, the ransomware will limit the victim’s
access to the computer system by either locking the system or removing access
to files through file encryption. Next, the victim will be instructed to pay a
ransom. The ransom is typically in the form of crypto-currency and is required
in order to regain access to their systems or files [1].

In this paper, we focus on tackling the file-encrypting ransomware that
encrypts a list of files on the victim’s computer. The popular modern adage,
“Data is gold”, depicts exactly why ransomware is so effective. Regardless of
industry, society has been steadily transitioning to a state of electronic and
data dependence. This dependence along with several leading factors have
created ideal conditions that have allowed ransomware to thrive. These key
factors include the viability in financial gain and the difficulties of
recovering from ransomware attacks. With a variety of crypto-currencies such
as Bitcoin becoming more economically established, it provides an avenue for
malicious actors to anonymously receive ransom payment without exposure. For
the average computer user, it is nearly impossible for them to recover their
data without payment. Even companies and tech savvy people must use extensive
resources to maintain backups in hope of recovery or else they will lose
valuable data. The difficulties of defending against ransomware and the
ability of malicious parties accepting payments anonymously have led to
disastrous results. Malicious parties from script kiddies to advance
persistent threats (APT) have successfully leveraged ransomware campaigns
against society. A prominent and possibly one of the most infamous ransomware
is WannaCry. WannaCry piggybacks off the NSA exploit, Eternal Blue, that was
release by the APT Shadow Brokers. In the course of a day, WannaCry had
infected an estimated 230,000+ computers and ultimately resulted in hundreds
of millions to billions of dollars worth of damage. Figure 1 is an example of
WannaCry’s ransom message. This message demands payment under threat of
permanent file loss.

Figure 1: WannaCry Ransomware

As aforementioned, the primary recovery strategy for a ransomware attack is to
restore the system using backups [2, 3, 4, 5]. There are many different back
up strategies, but they all require both storage space and time. Back up
strategies typically deal with a trade off between data availability and time.
Both businesses and home users must evaluate the costs and time associated
with maintaining up to date and reliable back ups. Real time back ups are
often far too expensive while other incremental strategies will still lead to
overhead in storage and management. In the event of a ransomware infection,
only the data from a back up will ensure data integrity. However, this too
leads into the issue of identifying when the ransomware first infiltrated the
system. If the ransomware remained dormant on the system prior to execution,
then previous backups will have dubious integrity. Thus, even with a
consistent backup routine, systems are still exposed and at risk to ransomware
attack. Furthermore, some variants of ransomware [6] have been documented to
also encrypt backups. Ultimately, back ups are a last defense strategy for
ransomware recovery.

Since existing recovery approaches are not always effective, efforts have been
devoted to the development of ransomware detection techniques that aim to
detect and stop the ransomware attack before it is able to encrypt all the
files. These detection techniques resemble antivirus software. They try to
identify potential ransomware attacks by identifying function calls in the
code [7, 8], analyzing file access patterns and network traffic [9], or
monitoring malicious changes to a small number of decoy files [10]. However,
current approaches still encumbered with various limitations. Many of them
reduce the computer system performance, require excessive storage space, or
produce excessive false positives. Moreover, they are generally susceptible to
novel forms of ransomware that have adapted to different detection algorithms
and exhibit new behavior.

In order to provide a more robust and effective defense against file-
encrypting ransomware, in this paper, we propose a novel hybrid method called
FREEDOM (Fast REcovEry and DetectiOn Mechanism), which possesses both recovery
and detection abilities. The uniqueness of FREEDOM is that it fights the virus
like a virus. Specifically, we leverage the Alternative Data Streams (ADS)
technique which is usually used by malicious applications, to develop a data
protection method that misleads the ransomware to attack only file ‘shells’
instead of the actual file content. With our proposed system in place, users
maintain ready access to their data without any perceived differences while
having their data in a secure, defensive and recoverable posture.
Additionally, our system is also resilient to white-box attacks. FREEDOM is
capable of detecting any illegitimate modification to the ADS style files by
utilizing operations conducted in the operating system kernel that cannot be
easily targeted by ransomware. We have evaluated a number of ransomware
samples and the experimental results demonstrate that our approach is an
effective defense against ransomware targeting users’ individual files. Our
contributions are summarized as follows:

  * •

We propose a novel defense mechanism called FREEDOM to fight against file-
encrypting ransomware. Unlike many existing recovery mechanisms, FREEDOM
introduces negligible performance overhead and requires nearly no additional
space.

  * •

We not only consider current file-encrypting ransomware but also emerging
ones. We propose a kernel-level monitoring algorithm which is capable of
detecting potentially malicious changes to our proposed new file structure,
thereby preventing ransomware targeting our method from causing data loss.

  * •

We have conducted extensive experiments on numerous real ransomware. The
findings demonstrate both the efficiency and effectiveness of the proposed
FREEDOM system.

The rest of the paper is organized as follows. Section II presents our
proposed FREEDOM system. Section III reports the experimental results. Section
IV analyzes the system security. Section V reviews related work on ransomware
defensive mechanisms. Finally. Section VI concludes the paper.

##  II The FREEDOM System

In this section, we introduce our proposed FREEDOM system that possesses
several unique features. First, FREEDOM is capable of quickly recovering from
existing file-encrypting ransomware attacks and guarantees zero file lost.
Here, zero files lost refers to the ability to restore all the user’s original
files using the FREEDOM system. Second, FREEDOM introduces negligible
operational overhead and users will not notice the existence of FREEDOM.
Third, FREEDOM requires almost no any additional storage space. Finally,
FREEDOM is also robust against future ransomware that are aware of the
mechanisms of FREEDOM.

The primary concept of the FREEDOM system is to obfuscate access to user files
by utilizing Alternative Data Streams (ADS). This is similar to the process
malware use to insert malicious code into ADS. However, unlike malware which
only needs to execute its own code in ADS, our FREEDOM system faces the
following new challenges:

  * •

How can FREEDOM ensure that user experience remains consistent when
interacting with the protected files? This is because ADS data is hidden from
users and cannot be directly accessed using common applications like Acrobat
or WORD. It is certainly not practical to require users to utilize special
commands to access their files.

  * •

How can FREEDOM be resilient against attackers who know the internal mechanism
of FREEDOM? In other words, if attackers know the users’ files are hidden in
ADS, can we prevent attackers from directly encrypting the ADS or make the
attack challenging enough such that it is effort prohibitive?

In order to address the listed challenges, the FREEDOM system consists of
three major components: an ADS file converter for file conversion, an ADS file
restorer which restores user files after a ransomware attack, and a kernel-
level driver monitor for detecting new types of ransomware. In what follows,
we will elaborate on their technical details.

###  II-A ADS File Converter

Since Alternative Data Stream (ADS) is the building block of our system, we
first briefly introduce its basic mechanisms. (ADS) is a file attribute in the
NTFS file. The NTFS file system has a Master File Table (MFT) that stores file
entries. Each entry in MFT describes a file. A file in NTFS is actually more
than one file. It is essentially a container that has a collection of
attributes stored as separate data streams (as illustrated in Figure 2). These
attributes include one default data attribute and multiple named data
attributes. The default data attribute usually stores the actual file content
(user data) or the index to the user data. This data attribute is the file
that users are most familiar with and deal with. The other named data
attributes are the so-called Alternative Data Streams (ADS), which are
internal to the NTFS system and not visible to users without special tools.
Not only invisible to users, changes in ADS do not even affect the file size.
Such obscure features make ADS an ideal vector for malware to insert their
malicious code. While malware can hide the code in ADS, we can also take
advantage of ADS’ obscure features to hide user data such that ransomware will
not be able to locate user data from traditional file searches. This is the
starting point of the design of our FREEDOM system.

Although relying on the same ADS technique, the design of FREEDOM system faces
many more challenges than malware. Malware only needs to hide one particular
piece of malicious code in an ADS attached to a legal file and does not need
to facilitate user access. On the contrary, our FREEDOM system not only needs
to hide user data of various file types .pdf, .docx, .xlsx, and .jpg, but must
also ensure that users can still operate these hidden files using the
corresponding applications. In order to avoid encumbering the user with
additional usage steps, all the file protection conducted by FREEDOM should be
automatic and require no extra expertise. In summary, the FREEDOM system is
required to be practical and user friendly. Ideally, when a user attempts to
open their original file, the original file content should be displayed and
editable through the associated application, e.g., a .docx file would be
opened by Microsoft WORD, and a .pdf file would be opened by Adobe Acrobat.

Figure 2: Normal File vs. PAUF File

To achieve the above goals, we propose a new file structure as shown in Figure
2 along with an ADS file converter that can automatically convert a user file
to the new file structure. Specifically, the new file structure, called
Protected ADS User File (PAUF), consists of two major components: a linker
file and an ADS file with user data. The conversion process from a regular
user file to the PAUF is as follows. Given a normal file, say sample.txt, the
content in sample.txt will first be copied to an ADS data stream named
“sample.txt:Data1.txt” using the following command.

cat sample.txt $>$ sample.txt:Data1.txt

Next, we create a linker file to provide access to the newly created ADS file.
The linker file will replace the original user file ’sample.txt’. In order to
allow users to perform normal file editions by double clicking the linker
files which have now taken place of their original files, the linker files
should contain commands that can automatically open the protected ADS user
file. However, this is very challenging. First, we need to select an
appropriate and widely available scripting language to support this automatic
file opening task. For this, we adopt Windows PowerShell which is a task
automation and configuration management framework from Microsoft, consisting
of a command-line shell and a scripting language. The second challenge is to
design a succinct and generic algorithm to save storage space and support
opening and editing different file types. As we know, user files have diverse
types and each type of file needs to be opened with certain applications. It
appears that a straightforward way is to use the PowerShell commands to
identify the original user file extension, search its associated application,
and then use that associated application to open the protected ADS user file.
However, this does not work as expected because most applications are not
designed to interact with ADS files and cannot save ADS files properly. For
example, Microsoft WORD will report the error stating that there are invalid
characters in the file path. This is because ADS files contain the special
symbol $:$ in the file path. To overcome this obstacle, we propose a work-
around approach which copies the ADS file to a temporary normal file to feed
to the application and then saves the modified file back to the ADS file.

Figure 3: Linker File Content Figure 4: Accessing the PAUF File

Figure 3 outlines the PowerShell commands in a linker file where $data1,
$data2 and $data3 refer to the linker file, the temporary file and the user’s
ADS file, respectively. Figure 4 illustrates the data access procedure.
Specifically, upon being double clicked, the linker file will perform the
following steps. First, create a new temporary file with the same extension as
the original user file. Next, copy the content of the protected ADS user file
to the temporary file. Then, invoke the application program for the temporary
file. The user can now see the content of the original file in the usual
application and interact with the file normally. After the user saves the
content in the application and closes it, this will trigger our system to
automatically copy the content from the temporary file to the protected ADS
user file. Finally, the temporary file is deleted from the system.

It is worth noting that our linker file contains universal commands that work
for any type of user files. This not only offers an easy deployment of our
system but also paves the foundation for detecting novel ransomware as
elaborated in Section II-C.

###  II-B ADS File Restorer

In this section, we focus on how to recover from existing ransomware attacks.
We will address the challenges of novel ransomware potentially designed to
target our defense mechanism in the next subsection.

Due to existing file-encrypting ransomware only targeting normal files (i.e.,
the default data streams) and the fact that the normal files are now protected
using our system, encrypting the linker file will not result in any user data
loss. This is due the linker file obscuring access to the actual user content
and thereby protecting the data. However, once a linker file has been
encrypted by ransomware, users will be unable to conventionally access their
data. Therefore, we still need a recovery mechanism to retrieve the user’s
original data following the attack.

To understand the file recovery process, we must be clear on how our proposed
Protected ADS User File (PAUF) is stored. One of our design goals is to
minimize the extra storage requirement. This allows our mechanism to be
significantly more cost effective when compared to many existing solutions
that require additional storage space for use data backups. In our FREEDOM
system, we take advantage of the pre-allocated space within a NTFS entry to
store the linker file so that the original user file size is unchanged.
Specifically, each file entry in the MFT is created with the same size, 1024
bytes, which are used to store file attributes including the default data
stream and the alternative data stream (ADS). The default data stream is used
to store user data while the ADS is used to store metadata such as the
original file author. There are two ways of storing user data in the file
entry. When the user data is small enough (much less than 1K bytes), the user
data will be directly stored in the default data stream of the MFT file entry
and be labeled as resident. In most cases the user data is larger than 1K
bytes and the file entry only records a pointer to the disk location where the
user data is stored. Such occurrences are labeled as non-resident. If a user
file is non-resident, i.e., not stored in the file entry, there is always
sufficient and unused space in the file entry to store our linker file due to
the linker file only requiring 264 bytes. Specifically, the default data
stream that is visible to users will be used to store the linker file. The
ADS, that is not visible to users, is used to store the pointer to the user
data.

If a user file is resident, the linker file is still stored in the default
data stream while the user data can be handled in two different ways according
to the data size. When the user file is very small and there is enough space
to place both the linker file and user data in the file entry, the user data
will be stored as an ADS in the file entry. When there is not enough space to
place both the user data and the linker file together in the file entry,
additional space outside the file entry will be required to store the user
data. In this case, the user data is less than 1K bytes, so the additional
space is less than 1K bytes as well. In reality, there are seldom user files
less than 1k bytes in size. Therefore, the need of additional storage space in
this occurrence can be considered negligible.

We now proceed to discuss how to restore user data after the system is
attacked by a file-encrypting ransomware. Existing file-encrypting ransomware
encrypts the default data streams in the file system. The actual user data is
still safe in the ADS. To restore system back to pre-attack state, we simply
carryout two steps. First, we locate all the ADS files that contain user data
using the command “dir /R”. Second, we replace each encrypted linker file with
our original linker file. Following these steps, the users regain conventional
access to their files. The recovered user data is free from any malicious
effects of ransomware execution.

###  II-C Kernel-level Driver Monitor

Our file protection approach introduced in the previous sections is very
effective against various versions of existing file-encrypting ransomware (as
shown in our experiments as well). The design is based on the fact that the
existing file-encrypting ransomware mainly target files that are visible
through traditional directory searches. However, there exists the possibility
that future ransomware may know of our implementation and attempt to target
the two components of the PAUF file, the linker and the ADS file. These
concerns are described as follows:

  * •

Attacking the linker file: A new ransomware may attempt to modify the commands
in the linker files to copy the user data in the ADS to their server and then
delete or encrypt the users’ ADS files.

  * •

Attacking the ADS file: A new ransomware may search for all the ADS files and
directly encrypt these ADS files which store the user data.

Figure 5: FREEDOM System with Driver Monitor and Proxy Application

In order to ensure resiliency against new ransomware, we propose a kernel-
level driver monitor to detect and prevent potential malicious modifications
to the PAUF files. Specifically, we implement the driver monitor using
commands from Windows Driver Kit (WDK) to monitor the I/O operations on the
linker files. Due to our linker files being uniform for all user data and that
linker files are not supposed to be modified, any write operations to the
linker files will be deemed as malicious. Our driver monitor checks I/O
operations to each process every two seconds and will terminate the process
that attempts to write to the linker files. This way, we can quickly stop the
attack to the linker files. We will also prompt an alert to the user detailing
the potential threat. This strategy not only works for preventing future
ransomware attacks, but also can be used to effectively terminate existing
ransomware when they attempt to perform write operations, i.e., encrypting the
linker files.

In order to ensure resiliency against new ransomware, we propose a kernel-
level driver monitor to detect and prevent potential malicious modifications
to the PAUF files. Specifically, we implement a driver monitor using Windows
Driver Kit commands to view and store I/O operations. We define any files
related to our PAUF files (linker and ADS), kernel-level driver, and FREEDOM
system application as important. All files other than these will be discarded
and not processed allowing our system to continuously monitor I/O operations
while lowering our overhead.

In the second attack scenario, our driver monitor will work in tandem with a
more advanced version of the linker file. The advanced linker file will not
contain the previous commands that copy the data between the temporary file
and the ADS file. Instead, theses commands are now compiled as an executable
file and the new linker file will call the executable file to perform the
operations on the user data. The advantage of introducing the executable file
as a proxy application is to enable the driver monitor to easily distinguish
malicious accesses from legal accesses to the user’s ADS files. In our system,
legal accesses to user’s ADS files should only be through the executable file
invoked by linker files. Since the executable file is non-editable, it is
impossible for the attacker to modify the executable file to perform
encryption. In order to encrypt the user’s ADS file, the attacker will have to
use their own application to access the user file. However, any access from
processes other than our designated proxy application will be deemed as
malicious by our driver monitor.

Figure 5 illustrates the PAUF file access procedure under the supervision of
the driver monitor. I/O operations to the linker file, the proxy application,
and the ADS files are continuously monitored. All deletion and modification
attempts to the linker files or the proxy applications are deemed malicious.
Additionally, all deletion and modification attempts to the ADS file performed
by applications other than the proxy are also deemed malicious. Not in the
scope of already treated files, our system also monitors modification attempts
to the file conversion methods and user interface program for our system. The
process that made the requested operation will be suspended. The user will
receive the alert to determine if they want to terminate the process. This
way, the user will also be informed of potential ransomware on their system.

Figure 6 shows the commands in the new linker file. The new linker file will
first gather the full path of the linker file and the full path of the
associated ADS file. Then, the linker file will call the proxy application,
i.e., the executable file, which handles further interaction with the user’s
ADS file. The proxy application will perform the same operations as the linker
file introduced in Section II-A. Specifically, the executable file will copy
the user data from the ADS file to a temporary file with the same extension as
the user’s original file so that the temporary file can be opened and edited
by its corresponding normal application. This means that means normal
applications will not directly access the user’s ADS files. By allowing only
our proxy application and other trusted Windows essential applications to
modify the ADS files, our driver monitor can easily identify malicious
applications that attempting to access the user data.

Figure 6: Advanced Linker File Content

It is worth noting that our driver monitor is substantially more accurate and
effective than other driver-based monitoring techniques [11, 12, 13, 14, 15,
16]. Although existing driver-based monitoring approaches also look at file
changes and monitor operations such as file writes, file reads, file
deletions, file creations, etc., they can only make educated guesses when
determining if a process is malicious through analysis of the system’s
historical normal behavior. They cannot guarantee to always detect a malicious
process. Moreover, for their drivers to identify malicious processes,
malicious behavior must be shown which allows ransomware to execute unhindered
until it passes a threshold that identifies it as a malicious process. This
causes a number of files to be encrypted or lost before their drivers can stop
the ransomware. Our FREEDOM system avoids these problems by design. We have a
unified linker file and a generic proxy application for all the user data.
This design consistency ensures high accuracy in classifying normal and
malicious operations on the user data as described in our detection algorithm.
In summary, any illegal operations are guaranteed to be detected by our driver
monitor.

Figures 7 and 8 show a simple example of how our FREEDOM system reacts to a
ransomware called GrandCrab. GrandCrab is one of few existing ransomware that
encrypt PowerShell files - the same file type as our linker files. In this
example, we first create a file called $MyFile.txt$ which contains a simple
sentence “This is my file data!”. Next, we convert the file into our PAUF
format. Figure 7 shows that the ADS file contains the same data as that in the
original user file. Finally, we allow the GrandCrab ransomware to run. Figure
8 shows the file content (highlighted) after the ransomware attack. Observe
that normal files, such as the original $MyFile.txt$, have now been encrypted
by the ransomware. However, our converted ADS file remains uninfected.
Moreover, if the driver monitor is turned on, it will detect the ransomware’s
attempt to encrypt the linker file and alert the user so that the user can
decide to terminate the malicious program.

Figure 7: Normal File and PAUF File Before Ransomware Attack Figure 8: Normal
File and ADS File After Ransomware Attack

##  III Performance Study

###  III-A Usability Evaluation

We have implemented all the components in the FREEDOM system including file
conversion, file restoration, the proxy application, and the kernel-level
driver. With our system modifying the type and storage of all user files, ease
of use must be considered. For this, we developed a GUI program (as shown in
Figure 9 that provides the functions to convert any file to our proposed PAUF
file format, revert PAUF files back to the normal format, and manage the
driver for the system. It is worth noting that this does not mean that a user
needs to perform all the functions each time he/she needs to access the file.
In practice, the user only needs to perform the file conversion function once
to convert files he/she would like to protect. Once the file conversion is
completed, the user can double click the converted files and edit them just
like normal files as many times as needed. Therefore, our system is much more
convenient for users than many security software that requires the user to
first decrypt or type in the password and later encrypt the file each time the
user edits the file.

The only time that the file conversion needs to be conducted again is when the
user wants to switch the application that is used to open a file. In our
current system, a linker file associates each file type with one frequently
used application for that file type. If a user wants to change the application
for a particular file, the linker file needs to be recreated to achieve that.
This is similar to the operation in Windows whereby a user needs to right-
click a file to set a new application to associate with a file type.

To sum up, although our system does not support the other way of file opening
by opening the application first and then selecting the file, our system does
not affect the user’s file editing operations inside the application, nor
affecting the user’s choice of applications. Additionally our system can be
implemented on a case by case method, files that do not need defense or do not
work easily with our system do not need to be converted and defended by our
system. With this in mind our system is best suited to defend files that
easily work within our system. Such use cases is defending Microsoft Office
Suite files on employee computers where they may not be fully trained to deal
with cyber security issues or may unknowingly infect their computer. In this
case important documents are protected between mandatory backups saving
important documents on an employee’s computer.

Figure 9: FREEDOM System GUI

###  III-B Effectiveness Evaluation

To evaluate the effectiveness of our FREEDOM system, we test it against 8
common file-encrypting ransomware: WannaCry, GandCrab, CryptoLocker-v3,
TeslaCrypt, Vipassana, Locky, JigSaw, and Cerber. They were downloaded from
the open source malware repositories [17, 18]. We would like to mention that
it is possible that the versions collected by these repositories are variants
of the original ransomware, but that should not affect the evaluation of the
effectiveness of our system.

In the experiments, we installed our FREEDOM system in a virtual machine with
a recently patched Windows 10 operating system. This environment emulates a
typical user system. The test environment contains traditional files of
various formats including: .txt, .jpg, .pdf, .docx, .xlxs, .pptx. We first run
the FREEDOM system to convert the traditional files to our PAUF file format.
Then, we disable the native antivirus and other defensive measures to evaluate
the sole effect of the ransomware infection under the defense of our FREEDOM
system.

In each round of experimentation, we have a freshly installed system as
described above. In each round we run a single ransomware and then examine the
following items:

  * •

Has any user’s ADS file been encrypted?

  * •

Has any linker file been encrypted when the driver monitor is turned off?

  * •

Has any linker file been encrypted when the driver monitor is turned on?

  * •

Has the ransomware been terminated by our driver monitor?

  * •

Are the user data recoverable after the attack? Here, the ability to recover
is defined as being able to restore the users’ access to their data to the
normal state without using software other than our FREEDOM system. No drive
recovery techniques or intensive inspection will be used for this process.

Figure 10 shows the experimental results. As expected, none of the ransomware
being tested encrypted the user’s ADS data. This is because a majority of
ransomware have a list of file extensions to encrypt and these file extensions
are usually those common file types that users often use to store their
personal data. From gathered research, many of the existing file-encrypting
ransomware do not intend to restrict the victim’s usage of the computer
system. Therefore, they do not target ADS files which are mainly for system
usage.

Figure 10: Ransomware Tests

We do see that some ransomware such as WannaCry and GrandCrab target a larger
list of file extensions that also include PowerShell files, e.g., our linker
files. In the experiments, when we use the original version of the linker file
(Section 2.1) without enabling the driver monitor, WannaCry and GranCrab will
encrypt these linker files. Once we switch to the advanced linker file version
along with the driver monitor, none of the linker files are encrypted by the
ransomware. Additionally, any ransomware that attempts to encrypt linker files
(e.g., WannaCry and GranCrab) have also been terminated by our driver monitor.
This proves the effectiveness of our driver monitor in detecting the malicious
operations on linker files. Even though we do not have any future ransomware
to test, the observed ability of the driver monitor in terminating ransomware
that attempt to encrypt the linker file indicates that our driver monitor will
be able to monitor malicious operations on the proxy application and ADS files
in a similar way. This demonstrates the potential of our system in defending
against future ransomware. It is worth noting that the success is attributed
to not only the driver monitor, but also the new PAUF file format which
enables clear classification of malicious behaviors.

It is not surprising to see that the driver monitor did not terminate
ransomware that does not encrypt linker files (or ADS files). This is because
they did not trigger the monitoring process which looks for malicious
operations on the linker files, the proxy application, and the ADS files. In
that case, it is inconsequential whether such ransomware is terminated since
none of the user’s critical files (i.e., PAUF files) has been encrypted by the
ransomware and no recovery is needed at all. In the event the linker files are
encrypted or damaged, the recovery process in our FREEDOM system is simple.
Our system can quickly replace the encrypted linker files (if any) with
original linker files to assist users in regaining access to their data.

###  III-C Efficiency Evaluation

Besides effectiveness, we also evaluate the possible overhead incurred by our
FREEDOM system during the file conversion and normal file operations. We
create files with different file extensions and sizes ranging from 10KB to
1GB. Note that our approach works for any type of files theoretically. In the
experiments, file tested are the common types including .txt, .jpg, .docx,
.pptx, .xlxs, .py, .cpp, .mp4, .mp3.

Figure 11 shows the average time for converting a single file of different
types on the virtual machine (8-core 4.2GHz CPU and 4GB memory) to our PAUF
file format. Observe that the file conversion is very fast. It takes less than
half second to convert files smaller than 100MB. When it comes to larger files
such as videos, the conversion still can be done in a matter of seconds (e.g.,
around 6s for 1 GB file). The conversion time is linear to the file size
mainly due to the need to copy the original file content to the ADS. The
creation of the small linker file is almost negligible. Since the majority of
files used daily, such as word documents and pictures, are typically less than
100MB, we expect the conversion during daily use will incur little overhead.
Additionally, the conversion can be done in the background and will not
inhibit user computer usage.

Figure 11: Average Time Taken to Convert a Normal File to a PAUF File

Next, we check if our system will affect user experience with respect to
opening and saving a file. Figure 12 shows the extra time needed to open and
save a PAUF file compared to the time taken to open and save a normal file of
the same size. As shown in the figure, preparing the opening and saving a PAUF
file require no more than half second of additional time when the file size is
less than 100MB. When the file size increases, the needed preparation and
saving time also increase, but they are still very fast (around 6s for a 1GB
file). This demonstrates the feasibility of our approach in practice. The
extra time is mainly introduced by the creation of the temporary normal file
during the PAUF file opening and saving processing. Recall that the FREEDOM
system uses the temporary files to automate the user’s access to the protected
ADS data. The temporary files are created based on the user’s ADS file content
with the goal to offer the users consistent interaction similar to how they
interact with normal files. Moreover, the file saving proceeds in the
background and users do not even have to experience this delay.

Figure 12: Extra Time of Opening or Saving a PAUF File

##  IV Security Analysis

There are three common types of ransomware: (i) screen locker which locks the
victim’s computer screen; (ii) hard drive encrypter which encrypts entire hard
drives in the victim’s computer; (iii) file encrypter which encrypts a list of
the victim’s personal files. Our proposed FREEDOM system is designed to
mitigate the existing file encrypters and future file encrypters.

While under the attack from existing file-encrypting ransomware, our FREEDOM
system will attempt to detect and terminate the attacks via the kernel-level
driver monitor as early as possible. As shown in the experiments, we
successfully terminated 7 out of 8 ransomware. Regardless of whether the
ransomware was able to be terminated, our file recovery mechanism will
guarantee consistent and successful results. Since existing file-encrypting
ransomware do not encrypt ADS files, all the user data is protected by our
FREEDOM system. We only need to replace the encrypted linker files with the
uniform linker file to restore users’ access to their data. In summary, our
FREEDOM system guarantees no file loss from existing file-encrypting
ransomware.

As previously discussed, a challenging problem will be to successfully defend
against ransomware developed to target the new file structure in our Freedom
system. We classify the potential attacks into the following categories:

  * •

Attempt to encrypt the user’s ADS file: With the FREEDOM system in place, the
user’s data is hidden in the ADS files. Therefore, a new ransomware may try to
find all the ADS files and encrypt them. However, such attack will not be
successful since user’s ADS files are only allowed to be accessed by our proxy
application. Any process other than our proxy application that attempts to
modify the ADS files will be suspended by our kernel-level driver monitor. An
prompt will be shown to the user to decide whether this process should be
terminated.

  * •

Attempt to modify or replace the proxy application: Since directly targeting
the user data in the ADS file is no longer a viable method of attack,
attackers may pivot to targeting the proxy application instead. However, since
the proxy application is an executable file, which is non-editable, the
attacker will not be able to modify the proxy application’s code. Moreover,
any modification to the proxy application can be easily blocked by our driver
monitor since the proxy application is not expected to be modified after
creation. Alternatively, if the attacker attempts to fully replace the
original proxy application with a malicious one, the replacement attempt will
also be noticed by our driver monitor since the proxy application is not
supposed to be deleted after creation. Any potential malicious replacement or
modification targeting the proxy application will be detected and prevented by
our driver monitor.

  * •

Attempt to modify or replace the linker files: Another possible attack is to
target the linker files. With the FREEDOM system in place, user’s data is
hidden in the ADS files and is only allowed to be modified through double
clicking the corresponding linker file. For new ransomware attempting to
encrypt the user’s ADS files, they may try to modify the original commands in
the linker files from normal execution to file encryption. However, such
attack will not be successful because any modifications to the existing linker
files will be detected by our kernel-level driver monitor since the linker
files are not supposed to be modified or deleted after they are created. This
also means attackers cannot delete the original linker files and replace them
with malicious ones.

  * •

Attempt to uninstall the kernel-level driver monitor: The last effort new
ransomware may attempt is to uninstall our kernel-level driver monitor so that
they can encrypt user’s ADS data without being detected. This will require the
ransomware to perform some type of privilege escalation and gain the
administrator rights. Once the ransomware obtains administrator rights, it can
effectively perform any operations it wants. In such an event, the ransomware
will be able to operate unhindered and other ransomware prevention and
mitigation strategies will be ineffective due to the possibility of being
uninstalled. Fortunately, 90% of existing ransomware strains do not seek
administrator rights [19]. We argue that although our FREEDOM system cannot
prevent ransomware that have the capability to gain administrator rights, the
requirement of administrator rights will significantly increase the
development cost of ransomware capable of targeting the FREEDOM system.

  * •

Attempt to encrypt the files during normal usage: This method of attack has
not been seen in any of the tested ransomware samples. This attack method
would involve ransomware gaining remote access to the user’s computer and
changing the files through our system by interacting with normal programs like
the standard user would. As our system treats this type of access as normal
user access, this would be seen as allowable. If an attacker went through each
file on the computer and changed them this way, they could encrypt the entire
file system. This method is extremely slow, is easily seen by any user on the
computer, and is not the normal mode of operations associated with ransomware.
Generally this attack would only be done in a targeted attack in which case
ransomware is most likely not the best usage. This type of attack is
considered outside the scope of our defense scheme as we are defending against
general automated forms of ransomware.

To sum up, our FREEDOM system is robust against existing file-encrypting
ransomware and future ransomware that do not seek administrator rights on the
victim’s computer.

##  V Related Work

Aside from user awareness training, the technological way of defending file-
encrypting ransomware can be classified into three main categories: (i)
backups; (ii) code analysis; and (iii) dynamic monitoring.

Data backup is a commonly adopted strategy to recover user data from malware
and ransomware attacks [20]. Several existing ransomware defense methods [2,
3, 4, 5] utilize different strategies to create secure backups on the system
and prevent the backups from being encrypted by ransomware. While creating
data backups are an effective solution to ransomware attacks, it comes with
heavy storage costs since a duplicate of user data needs to be maintained.
Additionally, if backups are not performed on regular basis, users will still
lose valuable data after the ransomware attack. Unlike any of the existing
backup methods, our proposed FREEDOM system neither needs to store duplicates
of user data nor require users to perform any regular backup.

Another strategy to defend the system against ransomware attack is code
analysis [21, 7, 22]. Code analysis relies upon static and dynamic analysis in
the effort to draw conclusions from an artifact based on the native
characteristics of ransomware. This is similar to an anti-virus software that
checks the hash of an executable against a known database of malware and
discerns if this may be a malware. These characteristics can also be used to
train classifiers or set up entropy measurements. However, the detection
accuracy of static analysis approaches are not guaranteed. This is evident
when examining anti-virus’ poor detection rate regarding novel or malware
variants.

A more advanced defense mechanism is dynamic monitoring [23]. Since ransomware
typically needs to access user files and modify them in a small time frame,
they make incredible amounts of system noise that is uncommon for any normal
use. Based on these observations, various dynamic analysis algorithms [12, 24,
15, 11, 25] have been proposed to detect potentially malicious behavior in the
system. Upon detection of abnormal activities, the suspected process will be
terminated to mitigate the impact on the system. For example, NAGuard [11]
operates by monitoring system I/O operations, analyzing the data, and
terminating the suspicious processes. Besides monitoring the system behavior,
Taylor et al [26] propose to monitor hardware sensor behavior. They studied
the relationship between increasing and decreasing sensor readings to draw
conclusions on what type of task the system is currently preforming. Another
thread of works on dynamic analysis monitors network-based traffic. As
ransomware usually utilizes the Internet to get keys for encryption, Cabaj et
al. [27] and Ahmadian et al. [28] leverage network monitoring to identify
ransomware while it makes calls. However, existing ransomware detection
mechanisms have two common limitations. First, their detection accuracy is not
guaranteed because the classification of malicious behavior is based on some
heuristic functions. There may be either false positives or false negatives.
Also, for the classifier to work, it takes time to collect and learn user’s
normal behavior. Second, for the detectors to identify malicious processes,
malicious behavior must be shown. This allows ransomware to execute unhindered
until it passes a threshold that identifies it as a malicious process. This
causes a number of files to be encrypted or lost before the detector can stop
the ransomware. These detection methods cannot terminate suspected behavior
too early since terminating processes incorrectly could cause problems to the
user or lead to system instability. In order to avoid sacrificing user files
for the detection, Continella et al. [13] propose to couple the procedures of
detection and recovery. Kharaz et al. [14] use a similar method, but create an
artificial environment for the detection. Even though such hybrid approach can
help protect user data during the detection, they still may not be able to
detect the new ransomware which does not carry any known features learned by
the detection system.

Compared to the previous works, our FREEDOM system does not have any of the
limitations metioned above. Attributed to our new file structure (i.e., the
linker file and the ADS user file), we guarantee 100% detection accuracy in
terms of identifying ransomware that attempt to modify users’ protected ADS
files. We do not sacrifice any user protected data in the detection process.
Our system is resilient against both existing and future file-encrypting
ransomware that do not gain administrator rights.

##  VI Conclusion

In this paper, we propose a novel approach called FREEDOM to fight against
file-encrypting ransomware. The biggest advantages of FREEDOM are that it does
not require extra storage space to save user data and introduces negligible
overhead. The design of FREEDOM leverages the stealth ability of Alternative
Data Stream (ADS) to form a new structure of the user data which will not be
infected by existing file-encrypting ransomware. Along with a novel kernel-
level driver monitor, our FREEDOM system also has the future potential to
defeat new file-encrypting ransomware that are aware of our underlying
mechanisms. This driver monitor is also unique in that it ensures 100%
detection accuracy which is attributed to the new data structure in the
FREEDOM system. We show that our system can successfully safeguard user data
against real ransomware and our experimental results also demonstrate the
efficiency of our system.

## References

  * [1] C. Simoiu, J. Bonneau, C. Gates, and S. Goel, “”i was told to buy a software or lose my computer. i ignored it”: A study of ransomware,” in _Fifteenth Symposium on Usable Privacy and Security (SOUPS 2019)_. Santa Clara, CA: USENIX Association, Aug. 2019. [Online]. Available: https://www.usenix.org/conference/soups2019/presentation/simoiu
  * [2] J. Huang, J. Xu, X. Xing, P. Liu, and M. K. Qureshi, “Flashguard: Leveraging intrinsic flash properties to defend against encryption ransomware,” _ACM SIGSAC Conference on Computer and Communications Security_ , pp. 2231–2244, 2017.
  * [3] S. Baek, Y. Jung, A. Mohaisen, S. Lee, and D. Nyang, “Ssd-insider: Internal defense of solid-state drive against ransomware with perfect data recovery,” _IEEE International Conference on Distributed Computing Systems (ICDCS)_ , pp. 875–884, 2018.
  * [4] D. Min, D. Park, J. Ahn, R. Walker, J. Lee, S. Park, and Y. Kim, “Amoeba: An autonomous backup and recovery ssd for ransomware attack defense,” _IEEE Computer Architecture Letters_ , vol. 17, no. 2, pp. 245–248, July 2018.
  * [5] K. P. Subedi, D. R. Budhathoki, B. Chen, and D. Dasgupta, “Rds3: Ransomware defense strategy by using stealthily spare space,” _IEEE Symposium Series on Computational Intelligence (SSCI)_ , 2017.
  * [6] C. Xiao, “New os x ransomware keranger infected transmission bittorrent client installer,” Mar 2016. [Online]. Available: https://unit42.paloaltonetworks.com/new-os-x-ransomware-keranger-infected-transmission-bittorrent-client-installer/
  * [7] S. Sheen and A. Yadav, “Ransomware detection by mining api call usage,” in _2018 International Conference on Advances in Computing, Communications and Informatics (ICACCI)_ , 2018, pp. 983–987.
  * [8] N. Hampton, Z. Baig, and S. Zeadally, “Ransomware behavioural analysis on windows platforms,” _Journal of Information Security and Applications_ , vol. 40, pp. 44 – 51, 2018. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S2214212617306506
  * [9] A. O. Almashhadani, M. Kaiiali, S. Sezer, and P. O’Kane, “A multi-classifier network-based crypto ransomware detection system: A case study of locky ransomware,” _IEEE Access_ , vol. 7, pp. 47 053–47 067, 2019.
  * [10] J. Gómez-Hernández, L. Álvarez González, and P. García-Teodoro, “R-locker: Thwarting ransomware action through a honeyfile-based approach,” _Computers & Security_, vol. 73, pp. 389 – 398, 2018. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S0167404817302560
  * [11] aviadyifrah, “Naguard,” https://github.com/aviadyifrah/NAGuard, 2018.
  * [12] P. T. K. R. B. B. N. Scaife, H. Carter, “Cryptolock (and drop it): Stopping ransomware attacks on user data,” _IEEE 36th International Conference on Distributed Computing Systems (ICDCS)_ , pp. 303–312, 2016.
  * [13] C. Andrea, G. Alessandro, Z. Giovanni, D. P. Giulio, B. Alessandro, Z. Stefano, and M. Federico, “Shieldfs: A self-healing, ransomware-aware filesystem,” in _Proceedings of the 32Nd Annual Conference on Computer Security Applications_ , ser. ACSAC ’16. New York, NY, USA: ACM, 2016, pp. 336–347. [Online]. Available: http://doi.acm.org/10.1145/2991079.2991110
  * [14] A. Kharaz, S. Arshad, C. Mulliner, W. Robertson, and E. Kirda, “UNVEIL: A large-scale, automated approach to detecting ransomware,” in _25th USENIX Security Symposium (USENIX Security 16)_. Austin, TX: USENIX Association, Aug. 2016, pp. 757–772. [Online]. Available: https://www.usenix.org/conference/usenixsecurity16/technical-sessions/presentation/kharaz
  * [15] H. R. S. M. M. Ahmadian, “2entfox: A framework for high survivable ransomwares detection,” _International Iranian Society of Cryptology Conference on Information Security and Cryptology (ISCISC)_ , 2016.
  * [16] I. Bibi, A. Akhunzada, J. Malik, G. Ahmed, and M. Raza, “An effective android ransomware detection through multi-factor feature filtration and recurrent neural network,” in _2019 UK/ China Emerging Technologies (UCET)_ , Aug 2019, pp. 1–4.
  * [17] “thezoo - a live malware repository,” https://github.com/ytisf/theZoo, 2019, gPLv3 License.
  * [18] “Virus share,” https://virusshare.com/, 2019.
  * [19] “90 per cent of ransomware can execute without administrator rights,” August. [Online]. Available: https://engageemployee.com/90-per-cent-ransomware-can-execute-without-administrator-rights/
  * [20] “Ransomware a growing enterprise threat a deep dive into ransomware’s evolution and why businesses can’t afford to ignore it,” https://go.crowdstrike.com/rs/281-OBQ-266/images/WhitepaperRansomware.pdf.
  * [21] I. Kara and M. Aydos, “Static and dynamic analysis of third generation cerber ransomware,” in _2018 International Congress on Big Data, Deep Learning and Fighting Cyber Terrorism (IBIGDELFT)_ , 2018, pp. 12–17.
  * [22] O.-M. Ori, N. Nir, E. Yuval, and R. Lior, “Dynamic malware analysis in the modern era—a state of the art survey,” _ACM Comput. Surv._ , vol. 52, no. 5, Sep. 2019. [Online]. Available: https://doi.org/10.1145/3329786
  * [23] S. I. A. S. T. Hirra Sultan, Aqeel Khalique, “A survey on ransomeware: Evolution, growth, and impact,” _International Journal of Advanced Research in Computer Science_ , vol. 9, no. 2, 2018.
  * [24] C. Moore, “Detecting ransomware with honeypot techniques,” _Proc. Cybersecurity Cyberforensics Conference_ , pp. 77–81, 2016.
  * [25] M. Routa, B. Benjamin, P. Aurélien, L. B. Hélène, C. Nora, and L. Jean-Louis, “Ransomware’s early mitigation mechanisms,” in _Proceedings of the 13th International Conference on Availability, Reliability and Security_ , ser. ARES 2018. New York, NY, USA: Association for Computing Machinery, 2018. [Online]. Available: https://doi.org/10.1145/3230833.3234691
  * [26] M. L. Taylor, K. N. Smith, and M. A. Thornton, “Sensor-based ransomware detection,” _Future Technologies Conference_ , 2017.
  * [27] K. Cabaj and W. Mazurczyk, “Using software-defined networking for ransomware mitigation: The case of cryptowall,” _IEEE Network_ , vol. 30, no. 6, pp. 14–20, 2016.
  * [28] M. M. Ahmadian, H. R. Shahriari, and S. M. Ghaffarian, “Connection-monitor & connection-breaker: A novel approach for prevention and detection of high survivable ransomwares,” _International Iranian Society of Cryptology Conference on Information Security and Cryptology (ISCISC)_ , no. 12th, pp. 79–84, 2015.