text:
\section{Introduction}
The theory of belief change is concerned with the way agents incorporate new information.  Typically, the focus is on new information that is given as a propositional formula.  In this paper, we are concerned with situations where an agent needs to revise by a conditional where the antecedent is almost certainly false.  More precisely, we consider antecedents that will not be believed given any finite amount of ``regular'' supporting evidence.  We represent the degree of belief in such formulas using Ordinal Conditional Functions that may take infinite values, and we provide an approach to conditional revision based on basic ordinal arithmetic.

This paper makes several contributions to existing work on belief change.\footnote{This paper contains results that have been published in \cite{Hunter15} and \cite{Hunter16}.}  First, we demonstrate that
a simple algebra of belief change in the finite case extends naturally to the infinite case, giving a form of belief improvement.
In the process, we demonstrate that there are natural examples in commonsense reasoning where multiple levels of infinite implausibility are actually useful.  In particular, we introduce a natural approach to revision by conditional statements with little in the way of new formal machinery.

\subsection{Motivating Example}
Consider the following claims:
\begin{enumerate}
\item $heavy$: Your dog is overweight.
\item $fly$: Your dog can fly.
\item $hollow | fly$:  If your dog can fly, then it has hollow bones.
\end{enumerate}
The first two claims are simple declarative statements.  But note that there is a clear difference in the amount of evidence needed to convince the agent to believe each claim.  For (1), it presumably takes some finite number of reports from a trusted source.  For (2), it seems unlikely that any finite number of reports would be convincing.  This statement is almost certainly false, though it is possible to imagine a situation that would convince an agent to believe it.

The third statement is a conditional with a highly unlikely antecedent.  Nevertheless, the perceived ``impossibility'' of (2) does not mean that (3) is free of content.  Revision by (3) should change an agent's beliefs in a counterfactual sense; they may need to change their beliefs about hollow bones in some hypothetical scenario.
Moreover, if ever the notion of flying dogs becomes believable, then this report will take on significance at the level of factual beliefs.  In this paper, we refer to claims such as (3) as {\em nearly counterfactual}.  We will provide a formal characterization of such claims, as well as a suitable approach to revision.

\section{Preliminaries}
\subsection{Belief Revision}
{\em Belief revision} is the belief change that occurs when new information is presented to an agent
with some prior, possibly contradictory, set of beliefs.  We assume an underlying propositional signature ${\mathbf P}$.  An interpretation over ${\mathbf P}$ is called a {\em state}, while a logically closed set of formulas over ${\mathbf P}$ is called a {\em belief set}.  A belief revision operator is a function that combines the initial belief set and a formula to produce a new belief set.

Formal approaches to belief revision typically require an agent to have some form of {\em ordering} or {\em ranking} that gives the relative plausibility of possible states.  For example, in the well-known AGM approach, total pre-orders over states are used to represent the perceived likelihood of each state \cite{AlchourronGardenforsMakinson85,KatsunoMendelzon92}.
Unfortunately, this approach does not handle the problem of {\em iterated belief revision}.  Related work has addressed
iterated revision by explicitly specifying how the ordering changes, rather than just the belief set \cite{DarwichePearl97,BoothMeyer06,JinThielscher07}.

\subsection{Ordinal Conditional Functions}
An ordinal conditional function (OCF) is a function that maps each state to an ordinal \cite{Spohn88,Williams94}.  In this approach, strength of belief is captured by ordinal precedence.  Hence, if $r$ is an OCF and $r(s) < r(t)$, then $s$ is a more plausible state than $t$.  There is an obvious advantage to this approach in that a ranking function is clearly more expressive than a total pre-oder.

While the orginal definition allows the range of an OCF to be the class of all ordinals, in existing work it is common
to restrict the range to the natural numbers, possibly with an additional symbol $\infty$ representing impossibility.  In this paper, we will actually use a slightly larger range; so we need to briefly review ordinal arithmetic.\footnote{
It is beyond the scope of this paper to give a complete treatment of infinite ordinals, and ordinal arithmetic.  In the discussion here, we skip over fundamental set theory, and the fact that order-types are defined in terms of set-containment.  We refer the reader to \cite{Devlin93} for an excellent introduction.}
For our purposes, it is sufficient to note that ordinals are actually sets defined by an ``order type.''  The finite ordinals are the natural numbers.  The order type of the natural number $n$ is unique, because it is the only ordinal that has exactly $n-1$ preceding ordinals.  The first infinite ordinal is $\omega$, the set of all natural numbers.  Every countably infinite subset of the natural numbers is order-isomorphic to $\omega$.

It is easy to construct a countably infinite set that is not order isomorphic to $\omega$:  just add another symbol $\infty$ at the end that is larger than every natural number.  The ordinal that defines the order type of this set is written $\omega+1$.  Similarly, there exists a distinct ordinal $\omega +n$ for any natural number $n$.  And if we add a complete copy of the natural numbers, then we have the ordinal $\omega+\omega$ which is normally written as $\omega \cdot 2$.  We can procede in this manner indefinitely to define a countably infinite sequence of ordinals.  By taking powers, we can get even more order types; we will not delve further into this topic.

Ordinal addition can be understood in terms of the informal discussion above.  Given ordinals $\alpha$ and $\beta$, the ordinal $\alpha+\beta$ has the order type obtained by taking a set with order type $\alpha$ and then appending a set with order type $\beta$ where all the elements of $\beta$ follow the elements of $\alpha$ in the underlying ordering.  For finite ordinals, this coincides with the usual notion of addition.  For infinite valued ordinals it does not.  Note for example that $1+\omega = \omega$; adding a number that precedes $0$ does not change the order type, because the resulting structure is isomorphic to the natural numbers.  On the other hand $\omega+1\ne\omega$.  So ordinal addition is not commutative.  It is also worth noting that ordinal subtraction is, in general, not well defined.  In particular, it is not possible to define subtraction by $\omega$.

\section{Belief Change as Ordinal Arithmetic}
Although our goal is to address revision by conditionals, we first introduce a simple approach to belief change based on the addition of ordinals.  This will allow us to precisely define the notion of a nearly counterfactual statement, which is important for the class of conditionals that we wish to consider.

\subsection{Restricted Domains}
The following definition allows us to define conditional functions over any set of ordinals.
\begin{definition}
Let $S$ be a non-empty set of states and let $\Gamma$ be a collection of ordinals.  A $\Gamma$-CF ( $\Gamma$ conditional function) over $S$ is a function $r:S\rightarrow\Gamma$ such that $r(s)=0$ for some state $s$.
\end{definition}
Note that the definition of $\Gamma$-CFs does not actually specify that $\Gamma$ is a {\em set}, because we do not wish to specify the underlying set theory in detail.

\begin{figure}
    \centering
    \includegraphics[width=3in]{pic.png}
    \caption{Visualizing $\omega^2$}
\end{figure}

Several special cases are immediate:
\begin{itemize}
\item Spohn's ordinal conditional functions are $\Omega$-CFs, where $\Omega$ is the collection of all ordinals.
\item The class of $\omega$-CFs coincides with the finite valued ranking functions common in the literature.
\item The class of $(\omega+1)$-CFs is the set of ranking functions that can take finite values, as well as the single ``impossible'' plausiblity value $\infty$.  This is essentially equivalent to the possibilistic logic framework of \cite{DuboisPrade04}, that uses the ``necessity measure'' of 0.
\end{itemize}
In this paper, we are primarily interested in the class of $\omega^2$-CFs.  Note that $\omega^2$ can be specified as follows:
$$\omega^2 = \bigcup\{\omega\cdot k + c \mid k,c\in\omega\}.$$
Hence, every element of $\omega^2$ can be written as $\omega\cdot k + c$ for some $k$ and $c$.  We think of these conditional functions as having countably many infinite levels of implausibility.  A picture of $\omega^2$ is shown in Figure 1.

If $r$ is a $\Gamma$-CF, we write
$$Bel(r) = \{x \mid r(x)=0\}.$$
The {\em degree of strength} of a conditional function $r$ is the least $n$ such that $n=r(v)$ for some $v\not\in Bel(r)$.  Hence, the degree of strength is a measure of how difficult it would be for an agent to abandon the currently believed set of states.

\subsection{Finite Arithmetic on Conditional Functions}
In the finite case, belief change can be captured through addition on ranking functions.  Some variant of the following definition has appeared previously in published work by several authors; it is restated here and translated to our terminology.
\begin{definition}\label{def:rev}
Let $r_1$ and $r_2$ be $\omega$-CFs over $S$, and let $m$ be the minimum value of $r_1+r_2$.  Then $r_1\bar{+}r_2$ is the function on $S$ defined as follows:
$$r_1 \bar{+} r_2(x) = r_1(x)+r_2(x)-m.$$
\end{definition}
It is easy to check that this operation is associative, commutative, and that every element is invertible in the sense that, for each $r$ there is an $r^{\prime}$ such that $r\bar{+}r^{\prime}=0$.  Therefore, in terms of algebra, we say that the class of $\omega$-CFs is an {\em abelian group} under $\bar{+}$.

Note that Spohn's {\em conditionalization} can be seen as a special case of this algebra on ranking functions.  Let $r_1$ be a finite plausibility function representing the initial beliefs of an agent.  Let $\phi$ be a formula, let $d$ be a positive integer, and let $r_2$ be the ranking function defined as follows:
\[
  r_2(s) = \left\{
                    \begin{array}{ll}
                           0 \mbox{ if } s\models\phi \\
                           d \mbox{ otherwise }
                    \end{array}
                    \right.\\
\]
Then $r_1 \bar{+} r_2$ is equivalent to Spohn's conditionalization of $r_1$ by $\phi$ with strength $d$.  Similarly, if $r_2$ takes only two values and the degree of strength of $r_2$ is strictly larger than the degree of strength of $r_1$, then $r_1 \bar{+}r_2$ is AGM revision.

This approach does not extend to larger classes of ordinals.
\begin{proposition}
Let $\beta$ be an ordinal such that $\omega\in\beta$.  Then $\bar{+}$ is not well-defined over the class of $\beta$-CFs.
\end{proposition}
The problem is that subtraction is not defined for all pairs of (infinite) ordinals.

\begin{example}
Consider the motivating example.  We can define the following $(\omega+1)-CFs$:
\[
    r_1(s) = \left\{
                    \begin{array}{ll}
                           0 \mbox{ if } s\models\{fly\} \\
                           \omega \mbox{ otherwise }
                    \end{array}
                    \right.\\
\]
\[
   r_2(s) = \left\{
                    \begin{array}{ll}
                           \omega \mbox{ if } s\models\{fly\} \\
                           0 \mbox{ otherwise. }
                    \end{array}
                    \right.\\
\]
Normalized addition of $r_1$ and $r_2$  requires us to calculate $\omega - \omega$.  But this subtraction is not defined, so the calculation can not be completed.
\end{example}

This problem could be avoided by removing the normalization, but the result would no longer be an OCF.  If we want to work with ranking functions that are closed under some form of addition, then we must either modify the definition, or we must relax the constraint that the pre-image of 0 is non-empty.  We opt for the former.

\subsection{Finite Zeroing}
We define an algebra over $\omega^2$-CFs based on {\em finite zeroing}.
The following relation will be useful in proving results.  In the definition, and in some future results, it is useful to
consider functions over ordinals that do not necessarily take
the value 0 for any argument.  We use the general term $\Gamma$ ranking to refer to an arbitrary function from $S$
to $\Gamma$.\footnote{Konieczny refers to this kind of OCF as a {\em free OCF.}\cite{Konieczny09}}

\begin{definition}
For $\Gamma$ rankings $r_1$ and $r_2$, we write $r_1\sim r_2$ just in case the following condition holds for every pair of states $s, t$
$$r_1(s) < r_ 1(t) \iff  r_2(s) < r_ 2(t).$$
\end{definition}
Clearly,
$\sim$ is an equivalence relation.

The intuition behind finite zeroing is that each conditional function can be categorized by its minimum value, in a manner that is useful for revision.   Given any $\omega^2$ ranking $r$, let $min(r)$ denote the minimum value $r(s)$.  Note that a minimum is guaranteed by the fact that the ordinals are well-ordered.
\begin{definition}
Let $r$ be an $\omega^2$ ranking with $\min(r)=\omega\cdot k + c$.  Then $k$ is the {\em degree} of $r$ and $c$ is the {\em finite shift}, written $deg(r)$ and $fin(r)$ respectively.
\end{definition}
We can use the degree and the finite shift to define the following operation.
\begin{definition}
Let $r$ be an $\omega^2$ ranking with $deg(r)=k$ and $fin(r)=c$.  Define $\bar{r}$ as follows.  Let $s$ be a state with $r(s)=\omega\cdot m + p$.
\begin{enumerate}
\item  If $m>k$, then $\bar{r}(s) = \omega\cdot(m-k)+c$.
\item If $m=k$, then $\bar{r}(s) = (p-c)$.
\end{enumerate}
\end{definition}
We call $\bar{r}$ the {\em finite zeroing} of $r$.  Intuitively, elements at the
``lowest level'' are normalized to zero and elements at higher levels are shifted down by the degree of $r$. The following result is easy to prove.
\begin{proposition}
If $r$ is an $\omega^2$ ranking, then $\bar{r}$ is a $\omega^2$-CF and $r\sim\bar{r}$.
\end{proposition}
Hence, the finite zeroing of any ranking is an equivalent $\omega^2$-CF.
We can now extend the definition of $*$ to $\omega^2$-CFs.
\begin{definition}
Let $r_1,r_2$ be $\omega^2$-CFs.  Then
$$r_1*r_2 = \overline{r_1+r_2}.$$
\end{definition}
Using this definition, $*$ is consistent with $\bar{+}$ for $\omega$-CFs.  Hence, $*$ can capture standard belief revision operators (e.g., AGM, DP) by restricting to finite values and setting the degree of strength
of each function appropriately.  This is the natural extension of revision, therefore, to the case that allows infinite plausibility values.

\begin{example}
The motivating example over $\{heavy,fly\}$ can be captured by the following function:
\[
    r(s) = \left\{
                    \begin{array}{ll}
                           \omega \mbox{ if } s\models fly\\
			10\mbox{ if } s\models heavy\wedge\neg fly\\
                           0 \mbox{ otherwise }
                    \end{array}
                    \right.\\
\]
We let $*^n$ to denote a finite iteration of the $*$ operator.
Suppose that, for each $V\in\{heavy,fly\}$, $r_V$ is an OCF such that $r_V(s)=2$ if and only if
$s\not\models V$.  The following are immediate:
\begin{itemize}
\item $r*^n r_{heavy}(s)=0$ iff $n\ge 5$.
\item $r*^n r_{fly}(s)\ne0$ for any $n$.
\end{itemize}
Hence, it takes 5 reports to convince the owner that their dog is overweight.  No finite number of reports will convince them that the dog can fly.
\end{example}

In the $\omega^2$ case, the algebra obtained is not identical to the finite case.
\begin{proposition}
The class of $\omega^2$-CFs is a non-abelian group under $*$.  (i.e. it is closed, associative, and every element has an inverse, but it is not commutative).
\end{proposition}
The fact that $*$ is not commutative has interesting consequences, as illustrated in the following example.

\begin{example}
Assume again that the vocabulary contains the predicates $\{heavy, fly\}$.  Define
\[
   r_1(s) = \left\{
                    \begin{array}{ll}
                           \omega \mbox{ if } s\models fly \\
                           0 \mbox{ otherwise }
                    \end{array}
                    \right.\\
\]
\[
   r_2(s) = \left\{
                    \begin{array}{ll}
                           0 \mbox{ if } s\models\neg heavy \wedge fly \\
                           1 \mbox{ if } s\models heavy \wedge fly\\
			2   \mbox{ otherwise. }
                    \end{array}
                    \right.\\
\]
Hence, $r_1$ says that an agent believes dogs can not fly; moreover the agent essentially believes that a flying dog is an impossibility.  On the other hand, $r_2$ says that an agent believes that light dogs can fly - although the the strength of belief in this claim is only finite.  Moreover, $r_2$ gives an ordering over less plausible states as well.
Note that both $r_1$ and $r_2$ can be either an initial belief state or an observation.  The following calculations are immediate.
\[
   r_1*r_2(s) = \left\{
                    \begin{array}{ll}
                           \omega \mbox{ if } s\models\neg heavy \wedge fly \\
                           \omega + 1 \mbox{ if } s\models heavy \wedge fly\\
			0   \mbox{ otherwise. }
                    \end{array}
                    \right.\\
\]
\[
   r_2*r_1(s) = \left\{
                    \begin{array}{ll}
                           \omega \mbox{ if } s=\{fly\} \\
                           0 \mbox{ otherwise. }
                    \end{array}
                    \right.\\
\]

\end{example}

What is the significance of this example?  It shows that conditional beliefs from an observation can be maintained at higher plausibility levels.  In both cases, the underlying agent will not believe dogs can fly following revision.  But the first revision allows the ordering of states to be refined somewhat at the conditional level.  The second revision, on the other hand, washes away the finite level distinctions in the original belief set.  This is similar to AGM revision in the sense that recent information seems to carry some particular weight.  However, the infinite jumps in plausibility outweigh the preference for recency.

\section{Nearly Counterfactual Reasoning}
\subsection{Motivation}
In this section, we demonstrate how infinite-valued ordinal conditional functions can be useful for reasoning about conditional statements.

\begin{example}
We return to the flying-dog example.  Suppose that we initially believe $\neg fly$ and $\neg hollow$; in other words, we believe that dogs do not fly and that dogs do not have hollow bones.   Now suppose we are told that flying dogs have hollow bones.  Informaly, we want to revise by the conditional statement $(hollow|fly)$.

Note that $(hollow|fly)$ actually does not give any new information about dogs.  This revision should not change the relative ordering of any worlds with a finite strength of belief.  However, it does result in a change of belief.
If one is later convinced of the existence of flying dogs, then the fact about hollow bones should be incorporated.
\end{example}

We refer to the reasoning in the preceding example as {\em nearly-counterfactual} revision.  It is essentially a form of counterfactual reasoning, in which hypothetical worlds are considered in isolation.  At the same time, however, we keep a form of conditional memory at higher ordinal levels.  This is not only useful for perspective altering revelations, but we argue it can also be useful for analogical reasoning.

One important feature that is typically taken as a requirement for conditional reasoning is the Ramsey Test.  In the context of revision by conditional statements, Kern-Isberner formulates the Ramsey Test as follows:
when revising by a conditional, one would like to ensure that revision by $(\psi|\phi)$ followed by a revision by $\phi$ should guarantee belief in $\psi$ \cite{Kern-Isberner99}.  We suggest that this formulation needs to be refined in order to be used in the case where infinite ranks are possible.

In the case of the flying dog, one is quite likely to accept the conditional $(hollow | fly)$ based on a single report with finite strength.  However, a single report of $fly$ with finite strength will not be believed.  If the antecedent of the conditional is ``very hard'' to believe, then we should not expect the Ramsey Test to hold without some additional condition on the strength of the subsequent report.  The problem, in a sense, is that the notion of believing a conditional is quite different than the notion of believing a fact.  In order to believe $(hollow|fly)$, we simply need to keep some kind of record of this fact for the unlikely case where we discover that flying dogs happen to exist.
On the other hand, in order to believe $fly$, we really need to make a significant change in our current world view.

\subsection{Levels of Implausibility}
Approaches to counterfactual reasoning are typically inspired to some degree by Lewis, who indicates that the truth of a counterfactual sentence is determined by its
truth in alternative worlds \cite{Lewis73}.  We can represent this idea with $\omega^2$-CFs.  At each limit ordinal $\omega\cdot k$, we essentially have an entirely new plausibility ordering.  As $k$ increases, each such ordering represents an increasingly implausible world.  However, a sufficiently strong observation can force our beliefs to jump to any of these unlikely worlds.  As such, these are not truly counterfactual worlds, because we admit the possibility that they may eventually be believed.

The important property that we can capture with $\omega^2$-CFs is the following:  there are some formulas that may
be true, yet we can not be convinced to believe them based on any finite number of pieces of ``weak evidence.''  This allows us to give the following formal definition of the term {\em nearly counterfactual}.
\begin{definition}
Let $r$ be an OCF.  A formula $\phi$ is nearly counterfactual with respect to $r$ just in case there is no
$\omega$-CF $r^{\prime}$ such that $Bel(r*r^{\prime})\models\phi$.
\end{definition}
The following is an immediate consequence of this definition.
\begin{proposition}
If $\phi$ is nearly counterfactual with respect to $r$, then there is no finite sequence $r_1,\dots,r_n$ of $\omega$-CFs such that $Bel(r*r_1*\cdots*r_n)\models\phi$.
\end{proposition}
We introduce some useful notation.
\begin{definition}
Let $\phi$ be a formula.  An OCF $r$ is a $\phi$-strengthening iff $Bel(r)=\{s\mid s\models\phi\}$.
\end{definition}
So, a $\phi$-strengthening is just a ranking function where the minimal states are exactly the models of $\phi$.    For any formula $\phi$, let $(\phi,n)$ be the $\phi$-strengthening of $\phi$ where models of $\phi$ have plausibility $0$ and every other state has plausibility $n$.

\begin{definition}
Let $r$ be an $\omega^2$-CF.  For any limit ordinal $\omega \cdot k$, let
$r_k$ be the following partial function:
\[
    r_k(s)= \left\{
                    \begin{array}{ll}
                           r(s) \mbox{, if } r(s)=\omega\cdot k + c \mbox{ for some } c\\
			\mbox{undefined otherwise}\\
                    \end{array}
                    \right.\\
\]
\end{definition}
Hence, $r_k$ is just the restriction of $r$ to those states with plausibility values at level $k$.  We say that $\phi$ is {\em believed} at level $k$ if $\{s \mid s\in \min(r_k)\}\models \phi$.  Let $poss(\phi)$ denote the set of natural numbers $k$ such that $s\models \phi$ for some $s$ in the domain of $r_k$.

We can now introduce a form of strengthening with nearly counterfactual conditionals.  In the definition, given an $\omega^2$-CF $r$, we let $deg(s)$ denote the value $k$ such that
$r(s)=\omega\cdot k +c$.
\begin{definition}
Let $r$ be an $\omega^2$-CF and let $\psi,\phi$ be formulas where $\phi$ is nearly counterfactual with respect to $r$.  Let $n\in\omega$.
\[
    r*(n,\psi|\phi)(s) = \left\{
                    \begin{array}{ll}
                           r(s) \mbox{, if } deg(s)\not\in poss(\phi)\\
			r*(\psi,n)(s) \mbox{ otherwise}\\
                    \end{array}
                    \right.\\
\]
\end{definition}
We call this function the $n$-stengthening of $\psi$ conditioned on $\phi$.
This function finds all levels of $r$ where $\phi$ is possible, and then strengthens $\psi$ at only those levels.

\begin{example}
Let $r$ again be the plausibility function
\[
    r(s) = \left\{
                    \begin{array}{ll}
                           \omega \mbox{ if } s\models fly\\
			10\mbox{ if } s\models heavy\wedge\neg fly\\
                           0 \mbox{ otherwise }
                    \end{array}
                    \right.\\
\]
It is easy to verify
that $fly$ is nearly counterfactual with respect to $r$.  Now suppose that we extend the vocabulary to include
the predicate symbol $hollow$.  Define a new function $r^{\prime}$ as follows:
\[
    r^{\prime}(s) = \left\{
                    \begin{array}{ll}
                           r(s) \mbox{, if } s\not\models hollow\\
			r(s)+1 \mbox{, if } s\models hollow\\
                    \end{array}
                    \right.\\
\]
This just says that we initally believe our dog does not have hollow bones; however, it is not particularly implausible.  It follows that:
\begin{itemize}
\item $r^{\prime}(s)=\omega$ if $s\models fly\wedge \neg hollow$.
\item $r^{\prime}(s)=\omega+1$ if $s\models fly\wedge hollow$.
\end{itemize}
From these results, it follows that:
\begin{itemize}
\item $r^{\prime}*(2,hollow|fly)(s) = r^{\prime}(s)$, if $s\not\models fly$.
\item $r^{\prime}*(2,hollow|fly)(s) = \omega$, if $s\models fly\wedge hollow$.
\item $r^{\prime}*(2,hollow|fly)(s) = \omega+1$, $s\models fly\wedge \neg hollow$.
\end{itemize}
So, roughly speaking, after strengthening by $(hollow|fly)$, we now believe that hollow bones are more plausible in all hypothetical situations where we believe flying dogs are possible.
\end{example}

Note that plausibility of a state is only changed at levels where $\phi$ is considered possible.  Since the definition is only applied to nearly counterfactual conditions, this means that only hypothetical states are affected by the strengthening.

It remains to move from conditional strengthening to conditional revision.  Recall that, for any $\omega^2$-CF with $\min(r)=\omega\cdot k + c$, we write $fin(r)=c$.
\begin{definition}
Let $r$ be an $\omega^2$-CF and let $\psi,\phi$ be formulas where $\phi$ is nearly counterfactual with respect to $r$.
\[
    r*(\psi|\phi)(s) = \left\{
                    \begin{array}{ll}
                           r(s) \mbox{, if } deg(s)\not\in poss(\phi)\\
			r*(\psi,fin(r_k))(s) \mbox{ if } r(s)=\omega \cdot k + c
                    \end{array}
                    \right.\\
\]
\end{definition}
Hence, for revision, we strengthen belief in $\psi$ by the least value that will ensure $\psi$ is believed at level $k$.

Under this definition, we satisfy a modified form of the Ramsey Test.
\begin{proposition}
Let $r$ be an $\omega^2$-CF and let $s$ be a state with $r(s)=\omega\cdot k + c$.  If $r^{\prime}$ is an $\omega^2$-CF with degree of strength larger than $k$ and $Bel(r^{\prime})\models \phi$, then
$$Bel((r * (\psi|\phi)) * r^{\prime})\models \psi.$$
\end{proposition}
Hence, if we revise by $(\psi|\phi)$ followed by an OCF with ``sufficiently strong'' belief in $\phi$, then $\psi$ will be believed.

\section{Relation to Existing Work}
\subsection{Infinite Plausibility Values}
There has been related work on the use of infinite valued ordinals in OCFs.  In particular, Konieczny defines
the notion of a {\em level} of belief explicitly in terms of limit ordinals\cite{Konieczny09}.  In this work, different ``levels'' are used to represent beliefs that
are independent in a precise sense.  The lowest level is used for representing an agents actual beliefs about the world, whereas higher levels are used to represent integrity constraints.  Our approach here is different in that we explicitly use the ordering on limit ordinals to represent infinite leaps in plausibility.  This work is also distinguished by the fact that we use ordinal arithmetic on a small class of ordinals to define a simple algebra of belief change.

\subsection{Belief Improvement}
The success postulate ($K*\phi\vdash\phi$) of the AGM framework is clearly incorrect in cases where evidence
is additive.  That is to say, there are situations where a single observation is not sufficient to convince an agent
to believe a particular fact.  {\em Improvement operators} \cite{Konieczny08} are belief change operators that address
this issue by introducing a new set of postulates.  The most important postulate states that an improvement
operator $\circ$ must have the property that:
\begin{itemize}
\item[{\bf (I1)}] {\em There exists $n\in\mathbf{N}$ such that } $B(\Psi\circ^n\phi)\vdash\phi$.
\end{itemize}
Here $\Psi$ is an epistemic state, and $B(\cdot)$ maps an epistemic state to the minimal elements of the underlying ordering.  Hence, an improvement operator has the property that an agent will be convinced to believe $\phi$ after a finite number of improvements.  The remaining postulates for a {\em weak improvement operator} are essentially
the DP postulates applied to the operation $\circ^n$ obtained from {\bf (I1)}.  We refer the reader to  \cite{Konieczny08} for the complete list of postulates.

We define an analog of  {\bf (I1)} as follows.  If $r_\phi$ denotes a $\phi$-strengthening, we can express
the condition as follows.
\begin{itemize}
\item[(I$^*$)] {\em There exists $n\in\mathbf{N}$ such that } $Bel(r*^nr_\phi)\models\phi$.
\end{itemize}
The truth of this property depends on the degrees of strength of the functions.

\begin{proposition}\label{rop}
If $r$ is an $\omega$-CF and $r_\phi$ is a $\phi$-strengthening with finite strength, then {\bf I$^*$} holds.
\end{proposition}
For an epistemic state $\Psi$ defined by $\prec_\Psi$, let $r_\Psi$ be the {\em canonical representation} of $\Psi$.\footnote{If $s$ is in the $n^{th}$ level of $\Psi$ , then $r_\Psi(s)=n$}  Define $\circ_n$ such that $\Psi\circ\phi$ is obtained by taking the ordering induced by $r_\Psi*r(\phi,n)$.
\begin{proposition}\label{pop}
For any $n\in\mathbf{N}$, the operator $\circ_n$ is a weak improvement operator.
\end{proposition}
We call $\circ_n$ a {\em finite improvement operator}, because the degree of strength is finite.  This result is essentially a corollary of Proposition \ref{rop}, and it suggests that our $*$ operation based on normalized addition is actually the natural extension of {\em improvement} to the setting of $\omega$-CFs.

The advantage of infinite plausibility values is that they give us greater flexibility in modelling improvement.
\begin{proposition}
If $r$ is an $\omega^2$-CF and $r_\phi$ is a $\phi$-strengthening with finite strength, then {\bf I$^*$} does not hold.
\end{proposition}
This result essentially states that ({\bf I1}) is not a sound property for $*$ if we allow infinite plausibility values.  This distinction can be seen in our running example.  There is no finite number of improvements
that will force the agent to believe that dogs can fly.

It is actually difficult to express the analog of Proposition \ref{pop} in the context of $\omega^2$-CFs, because a total pre-order over states can not capture the ``infinite jumps'' in plausibility encoded by $\omega^2$ ordinal ranks.  But it is possible to define a correspondence between sequences of orderings and ordinals in $\omega^2$.

\begin{definition}
Let $r$ be an $\omega^2$-CF where $\max(r)=\omega \cdot d + b$ for some $d, b$.  For $i\le d$, let $r_i$ denote the function defined as follows:
\begin{enumerate}
\item $domain(r_i)=\{s \mid r(s)=\omega\cdot i + c\}$.
\item If $r(s)=\omega\cdot i + c$, then $r_i(s) = c$.
\end{enumerate}
\end{definition}
The following propositions are immediate.
\begin{proposition}
Each $r_i$ is a $\omega$ ranking, and there exists an $\omega$-CF such that $r_i^{\prime}\sim r_i$
\end{proposition}
\begin{proposition}
For any $\omega^2$-CF $r$ over a vocabulary ${\mathbf P}$ with $deg(r)=d$, there is an extended vocabulary ${\mathbf P}_1$ and a sequence $r_0,\dots,r_d$ of $\omega$-CFs such that, for each $i\le d$, the $r_i$ is equivalent (i.e. $\sim$) to the restriction of $r$ to ordinals of degree $i$.
\end{proposition}
This result is proved by just extending the vocabulary appropriately with propositional variables that make each infinite jump in the ordinal value definable.  By breaking $r$ into a set of $\omega$-CFs, it follows that
{\bf (I$^*$)} holds at level $d$ when $r_\phi$ has degree of strength $\omega\cdot d$.  Therefore, belief change by normalized addition on $\omega^2$-CFs can really just be seen as a finite collection of improvements as each level.
The important point, however, is that no finite sequence of improvements at level $d$ will ever impact the actual beliefs at lower levels.

\subsection{Conditional Belief Revision}
Conditional belief revision was previously addressed by Kern-Isberner, who proposes a set of rationality postulates for conditional revision \cite{Kern-Isberner99}.  A concrete approach to conditional revision is also proposed, through
the following $\omega$-CF :
\[
    r*(\psi|\phi)(s) = \left\{
                    \begin{array}{ll}
                           r(s) - r(\psi|\phi) \mbox{, if } s\models \phi\wedge \psi\\
			r(s) + \alpha + 1 \mbox{, if } s\models \phi\wedge\neg \psi\\
			r(s) \mbox{, if } s\models\neg \phi\\
                    \end{array}
                    \right.\\
\]
where $\alpha=-1$ if $r(\{\phi,\psi\}) < r(\{\phi\})$, and $\alpha=0$ otherwise.  This operation satisfies all of the postulates for conditional revision, as well as the Ramsey Test.  We remark, however, that this approach is not well-defined if we allow infinite plausibility values because of the ordinal subtraction on the right hand side.  We suggest that this is not just a formal artefact of the theory; conditionals that are ''almost certainly'' false actually must be treated slightly differently.

In our approach, we essentially require the evidence for $\phi$ to be substantially stronger than the evidence for the conditional.  We suggest that our beliefs following conditional revision should be changed in sort of an infinitesimally small way.  While our beliefs about the actual world do not change, our beliefs about some (nearly) impossible world do, in fact, change.

Note that it is actually possible to reconcile our approach with Kern-Isberner's approach, by using the conditional revision above on each level $r_k$ of the initial OCF $r$.  At present, we are using a simple strengthening on each level, which actually flattens the plausibility structure after ordinal addition.  A combined approach could respect the infinite jumps in plausibility, while satisfying the postulates for conditional revision at each level.  We leave an investigation of this combined approach for future work.

\section{Discussion}
\subsection{Conclusion}
In this paper, we have explored the use of infinite ordinals for reasoning about belief change and conditional reasoning.  We have shown that allowing plausibility values to range over $\omega^2$ results in a belief algebra that is only slightly more complicated, and we gain an expressive advantage.  In particular, we can represent situations where stubbornly held beliefs are resistant to evidence to the contrary.  We have demonstrated that this results in a slightly more expressive class of improvement operators where evidence increases relative belief, but no finite number of improvements will actually lead to a change in the belief state.  Finally, we addressed so-called ``nearly counterfactual'' revision, where we incorporate information that is conditional on a highly unlikely statement.

\subsection{Future Work}
This paper is a preliminary exploration into different applications and formal properties of infinite valued ordinal conditional functions.  It remains to move beyond $\omega^2$-CFs, to completely characterize the relationship with improvement operators, and to consider further practical applications.

In the present framework, we have discussed nearly counterfactual reasoning as a tool for keeping a sort of ``memory'' about unlikely situations, in order to incorporate this information later if necessary.  But there is also a natural kind of reasoning that would allow us to use conditionals to reason by analogy about the actual state of the world.  Consider the following well-known ambiguity from
\cite{Lewis73}, and originally attributed to Quine:
\begin{enumerate}
\item If Caesar was president, he would use nuclear weapons.
\item If Caesar was president, he would use catapults.
\end{enumerate}
As a conditional, we could write both as $(W|C)$, where $W$ stands for a weapon that would be used and $C$ is the condition ``Caesar is president.''  But (1) suggests that we condition by imagining Caesar alive in the current world.  So this is a conditional statement interpreted in the current state of the world.  On the other hand, (2) suggests that we consider what would happen in some past world where Caesar exists.

Now suppose that we believe a certain politician is actually very similar to Caesar.  If we believe that Caesar would use nuclear weapons, then we may conclude that this ``real'' politician would also use nuclear weapons.  Formally, we could proceed as follows:  if some hypothetical world is isomorphic to the current state of the world when we restrict the vocabulary (to not include Caesar), then we can use inferences about the hypothetical world to draw conclusions about the actual world.  This is a form of {\em ampliative reasoning} that we intend to explore through $\omega^2$-CFs in future work.

\bibliographystyle{alpha}


text:
\section{Introduction}
\label{sec:intro}
Over the last two decades,
industrial systems have increasingly become the target of malicious actors~\cite{Duque_Anton.2017a}.
In the 1970's,
electronic components were introduced to automate control systems,
followed by \ac{scada} systems that allowed for reuse and reprogramming of components.
At that time,
security has not been an issue due to two reasons~\cite{Igure.2006}:
First,
industrial networks,
also known as \ac{ot},
are physically separated from \ac{it} networks.
Second,
\ac{ot} networks are highly application specific,
an attacker supposedly has no chance of understanding and influencing the processes.
However,
the rise of the \ac{iiot} and Industry 4.0 rendered both assumptions obsolete.
The fourth industrial revolution creates novel use cases,
e.g. the digital factory~\cite{STEF2013451},
mostly based on the increased capabilities in communication and embedded intelligence.
However,
these use cases require interconnectivity and distribution of data,
inherently breaking the above-mentioned assumptions.
This drastically increases the attack surface,
especially since most industrial communication protocols were not designed with security in mind.
Many of them,
such as \textit{Modbus}~\cite{Modbus.2012, ModbusIDA.2006} \textit{Profinet}~\cite{PROFIBUS.2017},
do not contain means for authentication or encryption.
As a consequence,
any attacker that has successfully broken the perimeter and moved laterally into the \ac{ot} network can listen and participate in the communication.
Breaking the perimeter of \ac{it} networks employed in the office area of industrial enterprises becomes the biggest hurdle for attackers and success in doing so leads to severe consequences,
e.g. the blackout in the Ukrainian power grid in December of 2015,
caused by a malware called \textit{Industroyer} or \textit{Crashoverride}~\cite{Cherepanov.2017, Dragos.2016, Lee.2016}.
Due to characteristics of \ac{ot} networks,
such as legacy devices,
but also periodic and unique behaviour,
\acp{ids} from the \ac{it} world cannot be transferred as they are.
Adaptions have to be made,
e.g. in creating industrial firewalls.
In this work,
methods based on machine learning as well as time series analysis are evaluated with respect to their capabilities to detect attacks in \ac{ot} networks.
The remainder of this work is structured as follows.
An overview of related work is provided in Section~\ref{sec:sota}.
The data sets used for the evaluation are introduced in Section~\ref{sec:data},
the algorithms implemented to detect the attacks are presented in Section~\ref{sec:algos}.
In Section~\ref{sec:eval},
the results are presented and discussed.
Finally,
this work is concluded in Section~\ref{sec:concl}.

\section{Related Work}
\label{sec:sota}
Due to the relevance of industrial enterprises to the national wealth of industrial nations and the severe potential impacts of \acp{cpps} on the physical world,
industrial intrusion detection has gained relevance in the research community.
\textit{Duque Anton et al.} have evaluated industrial network data with classifiers~\cite{Duque_Anton.2018b} as well as with time series-based methods~\cite{Duque_Anton.2018c}.
A survey regarding existing risk assessment methods is performed by \textit{Cherdantseva et al.},
as well as an assessment of the applicability of these methods in \ac{scada} scenarios~\cite{Cherdantseva.2016}.
\textit{Zhu et al.} provide an extensive overview of industrial \acp{ids} along several dimensions and compare security in \ac{it} and \ac{ot} networks~\cite{Zhu.2010}.
\textit{Garcia-Teodoro et al.} summarise challenges and solutions to anomaly detection in industrial networks~\cite{Garcia-Teodoro.2009}.
Attacks on industrial networks are analysed and evaluated by \textit{Caselli et al.}~\cite{Caselli.2015}.
\textit{Khalili and Sami} employ an a priori algorithm to detect attacks in industrial networks,
based on their regularity and knowledge about critical states~\cite{Khalili.2015}.
They focus on the timing behaviour of communication sequences that is expected to be regular in industrial environments.
\textit{Gao and Morris} address the detection of attacks in \textit{Modbus} communication with the help of an attack classification and terminology~\cite{Gao.2014}.
Another approach for detection in the legacy \textit{Modbus} communication is introduced by \textit{Morris et al.}~\cite{Morris.2012}.\\ \par
Wireless communication technologies are an enabler of novel business and application use cases for industry,
although wireless systems contain inherent attack surfaces.
A survey of intrusion detection in \acp{wsn} is performed by \textit{Butun et al.}~\cite{Butun.2014}.
\acp{manet} are a certain kind of wireless network,
addressed by \textit{Shakshuki et al.}~\cite{Shakshuki.2013}.
\textit{Wei et al.} employ a prediction-based intrusion detection system for wireless industrial networks~\cite{Wei.2013}.
\textit{Shin et al.} present methods of intrusion detection for such networks~\cite{Shin.2010},
commonly known as \acp{wsn}.
\textit{Zhang et al.} apply methods of intrusion detection to mobile networks~\cite{Zhang.2003}.
A roadmap for the use of machine learning-based anomaly detection methods in industrial networks is provided by \textit{Meshram and Haas}~\cite{Meshram.2017}.
\textit{Schuster et al.} propose a method for anomaly detection mechanisms based on learning a notion of normal behaviour~\cite{Schuster.2013}.
An evaluation of several machine learning methods for detecting malicious activities in \ac{scada} communication is provided by \textit{Beaver et al.}~\cite{Beaver.2013}.
\textit{Mukkamala et al.} analyse the \ac{darpa} \ac{kdd} cup '99 with neural networks and \acp{svm} in order to detect the attacks contained in the data set~\cite{Mukkamala.2002}.

\section{Data Set}
\label{sec:data}
In this work,
two distinct data sets are analysed with respect to detecting attacks.
The data sets are derived from different sources as well as processes and employ different protocols,
namely \textit{Modbus} and \ac{opcua}.
In the remainder of this work,
the \textit{Modbus}-based data set is referred to as \textit{DS1},
the \ac{opcua}-based one as \textit{DS2}.
An overview of both data sets can be found in Table~\ref{tab:data_sets_overview}.
\begin{table}[h!]
\renewcommand{\arraystretch}{1.3}
\caption{Data Sets Analysed in this Work}
\label{tab:data_sets_overview}
\centering
\scriptsize
\begin{tabular}{l l r r r r}
\toprule
\textbf{ID} & \textbf{Protocol} & \textbf{No. of Packets} & \textbf{Duration} & \textbf{Attacks} & \textbf{No. of mal. Packets} \\
\textit{DS1} & \textit{Modbus} & \numprint{274627} & 4 d &  & \numprint{60048} \\
\textit{DS2} & \ac{opcua} & \numprint{4910} & 41 m & 2 & \numprint{702} \\
\bottomrule
\end{tabular}
\end{table}

\subsection{\textit{Modbus}-based Data Set \textit{DS1}}
The \textit{Modbus}-based data set has been presented by \textit{Morris et al.}~\cite{Morris.2015}.
A gas pipeline has been set up in a simulation environment.
This data set is an extension of a previous work of \textit{Beaver et al.}~\cite{Beaver.2013} which contained attacks that have been easily discovered by machine learning algorithms.
The goal of this data set was to increase complexity and realism.
Overall,
the simulations consists of four parts:
A \ac{hmi},
a \ac{plc},
a network simulation and a virtual process.
It is shown that an \ac{hmi} and a \ac{mtu} respectively are used to control a control logic that,
in turn,
influences a pump and valve in a physical environment.
In order to follow a real physical process as closely as possible,
the \textit{Matlab Simulink} package \textit{SimHydraulics} (now called \textit{Simscape Fluids})~\cite{mathworks.} was used to simulate a pump,
a valve,
a pipeline and a fluid as well as its flow.
The simulation has been run for the duration of four days,
creating \numprint{274627} packets,
containing 20 features each.
In Table~\ref{tab:modbus_features},
the complete feature list is shown.
\begin{table}[h!]
\renewcommand{\arraystretch}{1.3}
\caption{Features Available in \textit{DS1}}
\label{tab:modbus_features}
\centering
\scriptsize
\begin{tabular}{l l}
\toprule
\textbf{Feature} & \textbf{Type}  \\
Address & Network information \\
Function Code & Command Payload \\
Length of Packet & Network Information \\
Setpoint & Command Payload \\
Gain & Command Payload \\
Reset Rate & Command Payload \\
Deadband & Command Payload \\
Cycle Time & Command Payload \\
Rate & Command Payload \\
System Mode & Command Payload \\
Control Scheme & Command Payload \\
Pump & Command Payload \\
Solenoid & Command Payload \\
Pressure Measurement & Response Payload \\
CRC Rate & Network Information \\
Command Response & Network Information \\
Time & Network Information \\
Binary Attack & Label \\
Categorised Attack & Label \\
Specific Attack & Label \\
\bottomrule
\end{tabular}
\end{table}
During this time,
a total of 60048 attacks has been performed,
belonging to one of 35 kinds of attack.
These attacks are clustered into seven categories as listed in Table~\ref{tab:modbus_attacks}.
The complete list can be found in the work of \textit{Morris et al.}~\cite{Morris.2015}.
\begin{table}[h!]
\renewcommand{\arraystretch}{1.3}
\caption{Categories of Attacks in \textit{DS1}}
\label{tab:modbus_attacks}
\centering
\scriptsize
\begin{tabular}{l r l}
\toprule
\textbf{Abbreviation} & \textbf{Label} & \textbf{Description}  \\
Normal & 0 & Normal Behaviour \\
NMRI & 1 & Naive Malicious Response Injection \\
CMRI & 2 & Complex Malicious Response Injection \\
MSCI & 3 & Malicious State Command Injection \\
MPCI & 4 & Malicious Parameter Command Injection \\
MFCI & 5 & Malicious Function Code Injection \\
DoS & 6 & Denial of Service \\
Recon & 7 & Reconnaissance \\
\bottomrule
\end{tabular}
\end{table}

\subsection{\textit{OPC UA}-based Data Set \textit{DS2}}
The \ac{opcua}-based data set analysed in this work is based on a real-world process environment introduced by \textit{Duque Anton et al.}~\cite{Duque_Anton.2019a}.
With the help of a \textit{Festo Didactic} environment,
the \textit{Festo Didactic MPS PA Compact Workstation},
a batch processing scenario is set up.
The water,
originally contained in \textit{Container 1},
is pumped into \textit{Container 2} by pump \textit{M102}.
Due to natural re-flow,
\textit{Container 2} is drained over time.
After the water level falls below a threshold value with a hysteresis,
the pump is restarted and pumps water from \textit{Container 1} into \textit{Container 2} again.
This normal behaviour is shown during the packets 0 to \numprint{1500},
from packet \numprint{1800} to packet \numprint{3000} and after packet \numprint{3500} in Figure~\ref{fig:opcua_normal_process}.
\begin{figure}[h!]
\centering
\includegraphics[width=0.48\textwidth]{opc_ua_mal_new.png}
\caption{Process Behaviour in \textit{DS2}}
\label{fig:opcua_normal_process}
\end{figure}
The attacks are from packet \numprint{1500} to packet \numprint{1800} and from packet \numprint{3000} to packet \numprint{3500},
marked by red frames.
In the first attack,
all sensor and actuator values are set to 0,
indicating an error in the process,
causing a disruption due to necessary investigation and maintenance.
For the second attack,
the frequency of the process is cut in half.
This causes a change in the process,
still indicating activity.

\section{Algorithms Used}
\label{sec:algos}
In this work,
\acp{svm} have been used to analyse the data sets as described in Section~\ref{sec:data} on packet basis.

\subsection{\acp{svm}}
\ac{svm} is a large margin classifier,
introduced by \textit{Boser et al.} in 1992~\cite{Boser.1992}.
Two classes of instances of dimensionality $n$ are divided by an $n+1$ dimensional hyperplane in a way that each instance has the maximal possible distance from the classifying hyperplane.
The instances are noted as tuples,
shown in (\ref{eq:svm_data})~\cite{Cortes.1995}.
\begin{equation}
\label{eq:svm_data}
\begin{split}
(x_{i}, y_{i}), i = 1, ..., m, y \in \{-1, 1\}
\end{split}
\end{equation}
$x$ is a vector describing an instance of data in an $n$-dimensional feature space.
$y$ describes the attribution of the instance as belonging to one of two classes,
while $m$ is the number of instances.
First,
the \ac{svm} is trained with a labeled set of instances.
It is a supervised classification method,
meaning the training set needs to contain information about the correct classes.
After training,
the attribution of the test and productive data is performed with the signum-function as shown in (\ref{eq:svm_attr}).
$w$ is the normal vector of the separator hyperplane,
$b$ is the offset from the hyperplane.
\begin{equation}
\label{eq:svm_attr}
\begin{split}
y_{i} = sgn(w, x_{i} - b)
\end{split}
\end{equation}
When applying \acp{svm},
obtaining a linear hyperplane to divide the data set is desirable.
However,
some data sets might not allow that.
In these cases,
the so-called \textit{kernel trick} can be applied~\cite{Cortes.1995}.
This \textit{kernel trick} can be used to map the input data space onto a higher dimensional feature space in a non linear fashion.
The higher dimensional data space then can be divided by a hyperplane in a linear fashion.

\subsection{\textit{Random Forests}}
\textit{Random Forests} are collections of \textit{Decision Trees},
binary classifiers consisting of one \textit{root} node,
several internal \textit{split} nodes and \textit{leaf} nodes that are used to classify events~\cite{Breiman.2001}.
The classification of the \textit{Random Forest} is done per majority vote of all \textit{Decision Trees}.
\textit{Random Forests} are robust to over-fitting and converge quickly,
making them applicable in a variety of use cases.
In addition to classifying data,
\textit{Random Forests} provide means to determine the relevance of features on the classification result.
This is done by measuring the decrease in accuracy if a feature is not considered for classification and the \textit{Gini} index respectively.
The \textit{Gini} index is a measure for the pureness of a data set that is split according to a certain feature~\cite{Rokach.2005}.
A high decrease in \textit{Gini} index indicates a high importance of the feature for a correct classification.
The decrease in accuracy is used to determine the feature relevance in Section~\ref{sec:eval}.

\section{Evaluation}
\label{sec:eval}
In this section,
the algorithms mentioned in Section~\ref{sec:algos} are applied to the data sets introduced in Section~\ref{sec:data}.
First,
the process of feature extraction is discussed and the features employed in anomaly detection are presented.
Furthermore,
the handling of missing data is addressed.
After that,
the performance of the respective algorithms is presented.

\subsection{Feature Selection}
Feature selection is useful in cases of large datasets where some features can be omitted without compromising on the accuracy of the classification model,
thereby resulting in reduced training time.
This is done by finding relationships in the data and analysing various processes that help in extracting such relations.
Selecting features that are capable of distinguishing between malicious and non-malicious instances is an important prerequisite to anomaly detection.
There are hardly formal methods to identify insightful features.
However,
there are approaches to identify the impact of a feature on the outcome,
e.g. with the importance score of \textit{Random Forests}~\cite{zhang2005network}.
In this work,
the features of \textit{DS1} have been analysed a priori.
These features and their relevance according to the importance score of \textit{Random Forests} are shown in Table~\ref{tab:ds1_feature_relevance}.
\begin{table}[h!]
\renewcommand{\arraystretch}{1.3}
\caption{Relevance of Individual Features in \textit{DS1}}
\label{tab:ds1_feature_relevance}
\centering
\scriptsize
\begin{tabular}{l l}
\toprule
\textbf{Feature} & \textbf{Relevance}  \\
Pressure & 0.177116 \\
Length & 0.134636 \\
CRC & 0.089498 \\
Cycle & 0.082905 \\
Reset & 0.082821 \\
Setpoint & 0.081545 \\
Function & 0.080561 \\
Gain & 0.068976 \\
Deadband & 0.060087\\
Rate & 0.039752\\
Command & 0.036751\\
System & 0.022929 \\
Pump & 0.021371 \\
Control & 0.010001 \\
Solenoid & 0.009587 \\
Address & 0.001463 \\
\bottomrule
\end{tabular}
\end{table}
Two variations of random forest classifiers were employed:
An ensemble with \ac{svm} by limiting the number of features for training the selection model and a classification of the full set of features for each dataset on plain random forest classifier.
On one hand,
a reduction of training time in using the ensemble classifier was observed.
On the other hand,
the random forest-only classifier resulted in a higher accuracy rate.
A perfect classification with no false positives or negatives is obtained for \textit{DS2}.
By using random forests before training the \ac{svm} model for \textit{DS1}
a reduction of training time by \numprint{5810} seconds is observed while still obtaining an accuracy of \numprint{92.5}\%.
It is shown that the pressure as well as the length of a packet have a high impact on the classification,
as listed in Table~\ref{tab:ds2_feature_relevance}.
\begin{table}[h!]
\renewcommand{\arraystretch}{1.3}
\caption{Relevance of Individual Features in \textit{DS2}}
\label{tab:ds2_feature_relevance}
\centering
\scriptsize
\begin{tabular}{l l}
\toprule
\textbf{Feature} & \textbf{Relevance}  \\
Water Temperature & 0.241810 \\
Water flow volume & 0.201617 \\
Water level container 1 & 0.160073 \\
Water level Container 2 & 0.156903 \\
Water pressure & 0.155168 \\
S111 & 0.034989 \\
S113 & 0.034306 \\
Pump running & 0.008172 \\
Pump status & 0.004048 \\
S112 & 0.002526 \\
B114 & 0.000387 \\
Ball valve acknowledge & 0.000000 \\
\bottomrule
\end{tabular}
\end{table}
The next five features are similarly important,
followed by two slightly less important features,
gain and deadband.
The remaining features are less important.
The data sets were split into training and testing data in a relation of 80\% to 20\%.
This relation is consistent for normal and malicious events in order to effectively train the classifiers on both classes.
Furthermore,
the data was pre-processed:
A \ac{pca} was applied in using \textit{Random Forests} and a zero mean scaling was used for \acp{svm}.

\subsection{Handling Missing Data}
Missing values in \textit{DS1} constitute 40\% of the entire dataset.
The sizeable amount makes it crucial to handle the data efficiently so as to not deteriorate the detection rate of the classifier.
Missing data is randomly spread across the features and is not specific to any one feature or the category of attack a packet belongs to,
thus classified as \ac{mcar}~\cite{schafer1998multiple}.
The missing data comes from the characteristic of \textit{Modbus} packets to not transfer all data values automatically,
but only those requested.
In order to obtain data at regular time points,
this lack of information on several time points is impacting the feature selection.
As it is safe to assume that the data does not behave erratically in between polling for the given data,
interpolation with time method is used for each feature of the dataset to estimate missing values as this method is efficient and most widely used~\cite{kreindler2016effects}.
The results indicate that interpolating missing values does not downgrade the accuracies of the different training models tested.
Since an attack may or may not impact all features at a single point in time,
each feature is considered to be an individual event.
For instance,
considering an MSCI attack,
an attack on the pump triggers random changes to the state of the pump,
whereas a solenoid attack randomly changes the state of the solenoid~\cite{Morris.2015}
The impact of an attack may eventually trickle down to other features in time.
However,
in this work,
only the point in time during which an attack occurs is discussed.
In \textit{DS2},
the dimensionality is lower.
From manual inspection of the features,
a few correlations are inferred.
To get an idea of the trends in all attacked records,
manual analysis is performed on the dataset.
The following direct correlations between a feature and an attack are drawn:
\begin{itemize}
\item Attacks have an influence of the following attributes: Water flow, water level in both containers, water pressure and water temperature
\item Pump status remains constant during an attack: 0 during the first attack and 1 during the second attack
\item \textit{S111} is 0 during the first attack and 1 during the second attack and normal operation
\item \textit{S112} 0 during the first attack and during normal operation
\item \textit{S113} is 0 during the first attack
\end{itemize}
These observations are supported by the feature importance scores derived from random forest classifier.
The features as shown in Table~\ref{tab:ds2_feature_relevance}.
Water temperature is the most relevant feature with about 25\%.
The following four features are important as well,
while the remaining features are significantly less relevant.

\subsection{Performance of the Algorithms}
Since both the datasets are highly imbalanced with only 21.9\% of events being attacks in  \textit{DS1} and 14.3\% in \textit{DS2},
modifications in support vector machine are employed to appropriately tackle the class imbalance problem.
An 80/20 split for training and testing data was chosen for the data sets.
For \textit{Random Forests},
\ac{pca} was applied as a pre-processing means while a zero mean scaling was performed for \acp{svm}.
For \textit{DS1},
cost sensitive learning for \ac{svm} modeling using \ac{svm}-weight is implemented~\cite{tang2009svms}.
When the classification model is assigned \ac{svm}-weight,
it assigns a larger penalty value to \acp{fn} than to \acp{fp}.
The training time for \ac{svm}-weight is the same as the training time required for \ac{svm} and is of order $\mathcal{O}((Np+Nn)^3)$,
where $Np$ are positive samples and $Nn$ are negative samples.
However overweighting the classifier increases the training time.
There are other data processing techniques such as under-sampling where only a subset of majority class is used for training along with minority class~\cite{drummond2003c4},
and oversampling where samples of minority class are replicated.
Since oversampling increase the dataset size and under-sampling could result in decrease of meaningful time dependent trends,
the cost metric of the classifier using recursive validation with \textit{Gridsearch}~\cite{GridSearch.},
a Python library,
was performed in the course of this work.
An overview of the performance of \acp{svm} on the data sets is provided in Table~\ref{tab:svm_performance}.
\begin{table}[h!]
\renewcommand{\arraystretch}{1.3}
\caption{Performance of \acp{svm}}
\label{tab:svm_performance}
\centering
\scriptsize
\begin{tabular}{l r l}
\toprule
\textbf{Metrics} & \textbf{\textit{DS1}} & \textbf{\textit{DS2}}  \\
Accuracy & 92.5\% & 90.8\% \\
Precision & 78.2\% & 90.4\% \\
Recall & 93.6\% & 99.9\% \\
F1 Score &  85.2\% & 94.9\%  \\
\bottomrule
\end{tabular}
\end{table}
With highly skewed distribution of the data,
evaluation of the classifier based only on accuracy is not sufficient.
Additional metrics,
such as precision,
recall and F1-score,
are employed to evaluate the classification ability.
The confusion matrix of each trained classifier is generated to compare predicted output labels to the existing ground truth.
The confusion matrix consists of the following metrics:
\ac{tp},
i.e. the number of correct classification of attacks,
\ac{tn}
i.e. the number of correct classification of normal instances,
\ac{fp},
i.e. the number of incorrect classification of normal instances as attacks,
and \ac{fn},
i.e. the number of incorrect classifications of attacks as normal instances.
In addition to \acp{svm},
\textit{Random Forests} were employed in order to classify the relevance of features and to detect attacks in the data set.
A summary of the evaluation is shown in Table~\ref{tab:eval_ov}.
\begin{table}[h!]
\renewcommand{\arraystretch}{1.3}
\caption{Summary of the Evaluation of Individual Methods}
\label{tab:eval_ov}
\centering
\scriptsize
\begin{tabular}{l r r c r r}
\toprule
& \multicolumn{2}{c}{\textbf{\textit{DS1}}} & \phantom{a} & \multicolumn{2}{c}{\textbf{\textit{DS2}}} \\
\cmidrule{2-3} \cmidrule{5-6}
\textbf{Method} & \textbf{Acc(\%) } & \textbf{Exec. time (s)} & & \textbf{Acc(\%)}& \textbf{Exec. time (s)}\\
\ac{svm} & 92.53 & 11712 & & 90.81 & 0.019\\
RF & 99.84 & 281 & &  99.98 & 52.31  \\
\bottomrule
\end{tabular}
\end{table}
The columns on the left describe \textit{DS1} while the columns on the right describe \textit{DS2}.
For both the datasets,
full feature models of \textit{Random Forest} classifiers worked well with accuracies of 99.7\% and 99.9\% for \textit{DS1} and \textit{DS2} respectively.
On setting a threshold to filter out least relevant features,
the accuracy of both the datasets reduced:
To 91\% when model was trained with  9 most important features for \textit{DS1} and 92\% when model was trained with ten most important features from the derived rankings.
The first data set,
\textit{DS1} consists of \textit{Modbus}-based traffic of a simulated process of a gas pump.
\textit{Random Forests} reach a significantly higher accuracy than \acp{svm} while exhibiting a more linear time behaviour.
As they converge quickly,
the take less time for the larger data set \textit{DS1}.

\section{Conclusion}
\label{sec:concl}
In this work,
two data sets captured in industrial environments are analysed for attack-based anomalies.
\acp{svm} are used to detect attacks of seven different categories and 35 different subtypes.
With accuracies and F1-scores of up to 92.5\% and 85.2\% respectively,
this approach is promising.
Lots of missing data in this data set do not impact the performance of the algorithms.
The second data set,
\textit{DS2} consists of \ac{opcua}-based traffic derived from a real-world hardware,
a \textit{Festo Didactic MPS PA Compact Workstation}.
In this case,
one class \acp{svm} are used,
as only two instances of attacks are present.
This leads to slightly worse accuracy of 90.8\%.
However,
due to an almost perfect recall,
the f1-score is performing pretty well with 94.9\%.
In this work,
handling of missing data as well as feature selection are addressed,
as real-world data often lacks features for some instances and contains noise and irrelevant information.
\textit{Random Forests} provide means to calculate the significance of individual features.
They can also be employed to detect anomalies in the data set,
with satisfactory results.
Additionally,
approaches such as \ac{pca} decrease the feature space and provide the most relevant features.
As attacks on industrial environments are occurring more frequent and becoming more critical in their effects,
effective detection is crucial.
Methods of machine learning,
such as \ac{svm} and \textit{Random Forests},
are capable of enhancing the detection capabilities of common industrial \acp{ids}.
Machine learning-based approaches profit from a limited state set in industry as well as a large amount of training data in a given environment,
as industrial environments produce loads of data.
The algorithms presented in this work do detect between 90\% and 95\% of the attacks in the data.
This will,
in practical application,
leave undetected attacks in industrial networks and thus pose security threats.
Additional means are required to enhance the level of security~\cite{Duque_Anton.2019b, Duque_Anton.2019d, Duque_Anton.2019e}.

redpajama_set_name: RedPajamaArXiv