# An Argumentation-Based Framework to Address the
Attribution Problem in Cyber-Warfare

Paulo Shakarian1 Gerardo I. Simari2 Geoffrey Moores1 Simon Parsons3 Marcelo A.
Falappa4
1Dept. of Electrical Engineering and Computer Science  U.S. Military Academy
West Point  NY
2Dept. of Computer Science  University of Oxford  Oxford  UK
3Dept. of Computer Science  University of Liverpool  Liverpool  UK
4Dep. de Cs. e Ing. de la Computación  Univ. Nac. del Sur  Bahía Blanca
Argentina and CONICET
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Attributing a cyber-operation through the use of multiple pieces of technical
evidence (i.e., malware reverse-engineering and source tracking) and
conventional intelligence sources (i.e., human or signals intelligence) is a
difficult problem not only due to the effort required to obtain evidence, but
the ease with which an adversary can plant false evidence. In this paper, we
introduce a formal reasoning system called the InCA (Intelligent Cyber
Attribution) framework that is designed to aid an analyst in the attribution
of a cyber-operation even when the available information is conflicting and/or
uncertain. Our approach combines argumentation-based reasoning, logic
programming, and probabilistic models to not only attribute an operation but
also explain to the analyst why the system reaches its conclusions.

##  1 Introduction

An important issue in cyber-warfare is the puzzle of determining who was
responsible for a given cyber-operation – be it an incident of attack,
reconnaissance, or information theft. This is known as the “attribution
problem” [1]. The difficulty of this problem stems not only from the amount of
effort required to find forensic clues but also the ease with which an
attacker can plant false clues to mislead security personnel. Further, while
techniques such as forensics and reverse-engineering [2], source tracking [3],
honeypots [4], and sinkholing [5] are commonly employed to find evidence that
can lead to attribution, it is unclear how this evidence is to be combined and
reasoned about. In a military setting, such evidence is augmented with normal
intelligence collection, such as human intelligence (HUMINT), signals
intelligence (SIGINT) and other means – this adds additional complications to
the task of attributing a given operation. Essentially, cyber-attribution is a
highly-technical intelligence analysis problem where an analyst must consider
a variety of sources, each with its associated level of confidence, to provide
a decision maker (e.g., a military commander) insight into who conducted a
given operation.

As it is well known that people’s ability to conduct intelligence analysis is
limited [6], and due to the highly technical nature of many cyber evidence-
gathering techniques, an automated reasoning system would be best suited for
the task. Such a system must be able to accomplish several goals, among which
we distinguish the following main capabilities:

  1. 1.

Reason about evidence in a formal, principled manner, i.e., relying on strong
mathematical foundations.

  2. 2.

Consider evidence for cyber attribution associated with some level of
probabilistic uncertainty.

  3. 3.

Consider logical rules that allow for the system to draw conclusions based on
certain pieces of evidence and iteratively apply such rules.

  4. 4.

Consider pieces of information that may not be compatible with each other,
decide which information is most relevant, and express why.

  5. 5.

Attribute a given cyber-operation based on the above-described features and
provide the analyst with the ability to understand how the system arrived at
that conclusion.

In this paper we present the InCA (Intelligent Cyber Attribution) framework,
which meets all of the above qualities. Our approach relies on several
techniques from the artificial intelligence community, including
argumentation, logic programming, and probabilistic reasoning. We first
outline the underlying mathematical framework and provide examples based on
real-world cases of cyber-attribution (cf. Section 2); then, in Sections 3 and
4, we formally present InCA and attribution queries, respectively. Finally, we
discuss conclusions and future work in Section 5.

##  2 Two Kinds of Models

Our approach relies on two separate models of the world. The first, called the
environmental model (EM) is used to describe the background knowledge and is
probabilistic in nature. The second one, called the analytical model (AM) is
used to analyze competing hypotheses that can account for a given phenomenon
(in this case, a cyber-operation). The EM must be consistent – this simply
means that there must exist a probability distribution over the possible
states of the world that satisfies all of the constraints in the model, as
well as the axioms of probability theory. On the contrary, the AM will allow
for contradictory information as the system must have the capability to reason
about competing explanations for a given cyber-operation. In general, the EM
contains knowledge such as evidence, intelligence reporting, or knowledge
about actors, software, and systems. The AM, on the other hand, contains ideas
the analyst concludes based on the information in the EM. Figure 1 gives some
examples of the types of information in the two models. Note that an analyst
(or automated system) could assign a probability to statements in the EM
column whereas statements in the AM column can be true or false depending on a
certain combination (or several possible combinations) of statements from the
EM. We now formally describe these two models as well as a technique for
annotating knowledge in the AM with information from the EM – these
annotations specify the conditions under which the various statements in the
AM can potentially be true.

EM | AM
---|---
“Malware X was compiled | “Malware X was compiled
on a system using the | on a system in English-
English language.” | speaking country Y.”
“Malware W and malware X | “Malware W and
were created in a similar | malware X are
coding style.” | related.”
“Country Y and country Z | “Country Y has a motive to
are currently at war.” | launch a cyber-attack against
| country Z.”
“Country Y has a significant | “Country Y has the capability
investment in math-science- | to conduct a cyber-attack.”
engineering (MSE) education.” |
Figure 1: Example observations – EM vs. AM.

Before describing the two models in detail, we first introduce the language
used to describe them. Variable and constant symbols represent items such as
computer systems, types of cyber operations, actors (e.g., nation states,
hacking groups), and other technical and/or intelligence information. The set
of all variable symbols is denoted with V, and the set of all constants is
denoted with C. For our framework, we shall require two subsets of C,
$\textsf{{C}}_{act}$ and $\textsf{{C}}_{ops}$, that specify the actors that
could conduct cyber-operations and the operations themselves, respectively. In
the examples in this paper, we will use capital letters to represent variables
(e.g., $X,Y,Z$). The constants in $\textsf{{C}}_{act}$ and
$\textsf{{C}}_{ops}$ that we use in the running example are specified in the
following example.

###### Example 2.1

The following (fictitious) actors and cyber-operations will be used in our
examples:

$\displaystyle\textsf{{C}}_{act}$ $\displaystyle=$
$\displaystyle\\{\mathit{baja},\mathit{krasnovia},\mathit{mojave}\\}$ (1)
$\displaystyle\textsf{{C}}_{ops}$ $\displaystyle=$
$\displaystyle\\{\mathit{worm123}\\}$ (2)

$\blacksquare$

The next component in the model is a set of predicate symbols. These
constructs can accept zero or more variables or constants as arguments, and
map to either true or false. Note that the EM and AM use separate sets of
predicate symbols – however, they can share variables and constants. The sets
of predicates for the EM and AM are denoted with
$\textsf{{{P}}}_{\textit{{EM}}},\textsf{{{P}}}_{\textit{{AM}}}$, respectively.
In InCA, we require $\textsf{{{P}}}_{\textit{{AM}}}$ to include the binary
predicate $\mathit{condOp}(X,Y)$, where $X$ is an actor and $Y$ is a cyber-
operation. Intuitively, this means that actor $X$ conducted operation $Y$. For
instance, $\mathit{condOp}(\mathit{baja},\mathit{worm123})$ is true if
$\mathit{baja}$ was responsible for cyber-operation $\mathit{worm123}$. A
sample set of predicate symbols for the analysis of a cyber attack between two
states over contention of a particular industry is shown in Figure 2; these
will be used in examples throughout the paper.

$\textsf{{{P}}}_{\textit{{EM}}}$: $\mathit{origIP}(M,X)$ Malware $M$
originated from an IP address belonging to actor $X$. $\mathit{malwInOp}(M,O)$
Malware $M$ was used in cyber-operation $O$. $\mathit{mwHint}(M,X)$ Malware
$M$ contained a hint that it was created by actor $X$.
$\mathit{compilLang}(M,C)$ Malware $M$ was compiled in a system that used
language $C$. $\mathit{nativLang}(X,C)$ Language $C$ is the native language of
actor $X$. $\mathit{inLgConf}(X,X^{\prime})$ Actors $X$ and $X^{\prime}$ are
in a larger conflict with each other. $\mathit{mseTT}(X,N)$ There are at least
$N$ number of top-tier math-science-engineering universities in country $X$.
$\mathit{infGovSys}(X,M)$ Systems belonging to actor $X$ were infected with
malware $M$. $\mathit{cybCapAge}(X,N)$ Actor $X$ has had a cyber-warfare
capability for $N$ years or less. $\mathit{govCybLab}(X)$ Actor $X$ has a
government cyber-security lab. $\textsf{{{P}}}_{\textit{{AM}}}$:
$\mathit{condOp}(X,O)$ Actor $X$ conducted cyber-operation $O$.
$\mathit{evidOf}(X,O)$ There is evidence that actor $X$ conducted cyber-
operation $O$. $\mathit{motiv}(X,X^{\prime})$ Actor $X$ had a motive to launch
a cyber-attack against actor $X^{\prime}$. $\mathit{isCap}(X,O)$ Actor $X$ is
capable of conducting cyber-operation $O$. $\mathit{tgt}(X,O)$ Actor $X$ was
the target of cyber-operation $O$. $\mathit{hasMseInvest}(X)$ Actor $X$ has a
significant investment in math-science-engineering education.
$\mathit{expCw}(X)$ Actor $X$ has experience in conducting cyber-operations.

Figure 2: Predicate definitions for the environment and analytical models in
the running example.

A construct formed with a predicate and constants as arguments is known as a
ground atom (we shall often deal with ground atoms). The sets of all ground
atoms for EM and AM are denoted with $\textsf{{{G}}}_{\textit{{EM}}}$ and
$\textsf{{{G}}}_{\textit{{AM}}}$, respectively.

###### Example 2.2

The following are examples of ground atoms over the predicates given in Figure
2.

$\displaystyle\textsf{{{G}}}_{\textit{{EM}}}:$
$\displaystyle\mathit{origIP}(\mathit{mw123sam1},\mathit{krasnovia}),$
$\displaystyle\mathit{mwHint}(\mathit{mw123sam1},\mathit{krasnovia}),$
$\displaystyle\mathit{inLgConf}(\mathit{krasnovia},\mathit{baja}),$
$\displaystyle\mathit{mseTT}(\mathit{krasnovia},2)$
$\displaystyle\textsf{{{G}}}_{\textit{{AM}}}:$
$\displaystyle\mathit{evidOf}(\mathit{mojave},\mathit{worm123}),$
$\displaystyle\mathit{motiv}(\mathit{baja},\mathit{krasnovia}),$
$\displaystyle\mathit{expCw}(\mathit{baja}),$
$\displaystyle\mathit{tgt}(\mathit{krasnovia},\mathit{worm123})$

$\blacksquare$

For a given set of ground atoms, a world is a subset of the atoms that are
considered to be true (ground atoms not in the world are false). Hence, there
are $2^{|\textsf{{{G}}}_{\textit{{EM}}}|}$ possible worlds in the EM and
$2^{|\textsf{{{G}}}_{\textit{{AM}}}|}$ worlds in the AM, denoted with
$\mathcal{W}_{\textit{{EM}}}$ and $\mathcal{W}_{\textit{{AM}}}$, respectively.

Clearly, even a moderate number of ground atoms can yield an enormous number
of worlds to explore. One way to reduce the number of worlds is to include
integrity constraints, which allow us to eliminate certain worlds from
consideration – they simply are not possible in the setting being modeled. Our
principle integrity constraint will be of the form:

$\textsf{oneOf}(\mathcal{A}^{\prime})$

where $\mathcal{A}^{\prime}$ is a subset of ground atoms. Intuitively, this
says that any world where more than one of the atoms from set
$\mathcal{A}^{\prime}$ appear is invalid. Let
$\textsf{{{IC}}}_{\textit{{EM}}}$ and $\textsf{{{IC}}}_{\textit{{AM}}}$ be the
sets of integrity constraints for the EM and AM, respectively, and the sets of
worlds that conform to these constraints be
$\mathcal{W}_{\textit{{EM}}}(\textsf{{{IC}}}_{\textit{{EM}}}),\mathcal{W}_{\textit{{AM}}}(\textsf{{{IC}}}_{\textit{{AM}}})$,
respectively.

Atoms can also be combined into formulas using standard logical connectives:
conjunction (and), disjunction (or), and negation (not). These are written
using the symbols $\wedge,\vee,\neg$, respectively. We say a world ($w$)
satisfies a formula ($f$), written $w\models f$, based on the following
inductive definition:

  * •

if $f$ is a single atom, then $w\models f$ iff $f\in w$;

  * •

if $f=\neg f^{\prime}$ then $w\models f$ iff $w\not\models f^{\prime}$;

  * •

if $f=f^{\prime}\wedge f^{\prime\prime}$ then $w\models f$ iff $w\models
f^{\prime}$ and $w\models f^{\prime\prime}$; and

  * •

if $f=f^{\prime}\vee f^{\prime\prime}$ then $w\models f$ iff $w\models
f^{\prime}$ or $w\models f^{\prime\prime}$.

We use the notation $formula_{EM},formula_{AM}$ to denote the set of all
possible (ground) formulas in the EM and AM, respectively. Also, note that we
use the notation $\top,\bot$ to represent tautologies (formulas that are true
in all worlds) and contradictions (formulas that are false in all worlds),
respectively.

###  2.1 Environmental Model

In this section we describe the first of the two models, namely the EM or
environmental model. This model is largely based on the probabilistic logic of
[7], which we now briefly review.

First, we define a probabilistic formula that consists of a formula $f$ over
atoms from $\textsf{{{G}}}_{\textit{{EM}}}$, a real number $p$ in the interval
$[0,1]$, and an error tolerance $\epsilon\in[0,\min(p,1-p)]$. A probabilistic
formula is written as: $f:p\pm\epsilon$. Intuitively, this statement is
interpreted as “formula $f$ is true with probability between $p-\epsilon$ and
$p+\epsilon$” – note that we make no statement about the probability
distribution over this interval. The uncertainty regarding the probability
values stems from the fact that certain assumptions (such as probabilistic
independence) may not be suitable in the environment being modeled.

###### Example 2.3

To continue our running example, consider the following set
$\Pi_{\mathit{EM}}$:

$\displaystyle f_{1}$ $\displaystyle=$
$\displaystyle\mathit{govCybLab}(\mathit{baja}):0.8\pm 0.1$ $\displaystyle
f_{2}$ $\displaystyle=$
$\displaystyle\mathit{cybCapAge}(\mathit{baja},5):0.2\pm 0.1$ $\displaystyle
f_{3}$ $\displaystyle=$ $\displaystyle\mathit{mseTT}(\mathit{baja},2):0.8\pm
0.1$ $\displaystyle f_{4}$ $\displaystyle=$
$\displaystyle\mathit{mwHint}(\mathit{mw123sam1},\mathit{mojave})$
$\displaystyle\mbox{}\wedge\mathit{compilLang}(\mathit{worm123},\mathit{english}):0.7\pm
0.2$ $\displaystyle f_{5}$ $\displaystyle=$
$\displaystyle\mathit{malwInOp}(\mathit{mw123sam1},\mathit{worm123})$
$\displaystyle\mbox{}\wedge\mathit{malwareRel}(\mathit{mw123sam1},\mathit{mw123sam2})$
$\displaystyle\mbox{}\wedge\mathit{mwHint}(\mathit{mw123sam2},\mathit{mojave}):0.6\pm
0.1$ $\displaystyle f_{6}$ $\displaystyle=$
$\displaystyle\mathit{inLgConf}(\mathit{baja},\mathit{krasnovia})$
$\displaystyle\mbox{}\vee\neg\mathit{cooper}(\mathit{baja},\mathit{krasnovia}):0.9\pm
0.1$ $\displaystyle f_{7}$ $\displaystyle=$
$\displaystyle\mathit{origIP}(\mathit{mw123sam1},\mathit{baja}):1\pm 0$

Throughout the paper, let
$\Pi_{\mathit{EM}}^{\prime}=\\{f_{1},f_{2},f_{3}\\}$. $\blacksquare$

We now consider a probability distribution Pr over the set
$\mathcal{W}_{\textit{{EM}}}(\textsf{{{IC}}}_{\textit{{EM}}})$. We say that Pr
satisfies probabilistic formula $f:p\pm\epsilon$ iff the following holds:
$p-\epsilon\leq\sum_{w\in\mathcal{W}_{\textit{{EM}}}(\textsf{{{IC}}}_{\textit{{EM}}})}\textsf{{Pr}}(w)\leq
p+\epsilon.$ A set $\Pi_{\mathit{EM}}$ of probabilistic formulas is called a
knowledge base. We say that a probability distribution over
$\mathcal{W}_{\textit{{EM}}}(\textsf{{{IC}}}_{\textit{{EM}}})$ _satisfies_
$\Pi_{\mathit{EM}}$ if and only if it satisfies all probabilistic formulas in
$\Pi_{\mathit{EM}}$.

It is possible to create probabilistic knowledge bases for which there is no
satisfying probability distribution. The following is a simple example of
this:

$\displaystyle\mathit{condOp}(\mathit{krasnovia},\mathit{worm123})$
$\displaystyle\mbox{}\vee\mathit{condOp}(\mathit{baja},\mathit{worm123}):0.4\pm
0;$ $\displaystyle\mathit{condOp}(\mathit{krasnovia},\mathit{worm123})$
$\displaystyle\mbox{}\wedge\mathit{condOp}(\mathit{baja},\mathit{worm123}):0.6\pm
0.1.$

Formulas and knowledge bases of this sort are inconsistent. In this paper, we
assume that information is properly extracted from a set of historic data and
hence consistent; (recall that inconsistent information can only be handled in
the AM, not the EM). A consistent knowledge base could also be obtained as a
result of curation by experts, such that all inconsistencies were removed –
see [8, 9] for algorithms for learning rules of this type.

The main kind of query that we require for the probabilistic model is the
maximum entailment problem: given a knowledge base $\Pi_{\mathit{EM}}$ and a
(non-probabilistic) formula $q$, identify $p,\epsilon$ such that all valid
probability distributions Pr that satisfy $\Pi_{\mathit{EM}}$ also satisfy
$q:p\pm\epsilon$, and there does not exist $p^{\prime},\epsilon^{\prime}$ s.t.
$[p-\epsilon,p+\epsilon]\supset[p^{\prime}-\epsilon^{\prime},p^{\prime}+\epsilon^{\prime}]$,
where all probability distributions Pr that satisfy $\Pi_{\mathit{EM}}$ also
satisfy $q:p^{\prime}\pm\epsilon^{\prime}$. That is, given $q$, can we
determine the probability (with maximum tolerance) of statement $q$ given the
information in $\Pi_{\mathit{EM}}$? The approach adopted in [7] to solve this
problem works as follows. First, we must solve the linear program defined
next.

######  Definition 2.1 (EM-LP-MIN)

Given a knowledge base $\Pi_{\mathit{EM}}$ and a formula $q$:

  * •

create a variable $x_{i}$ for each
$w_{i}\in\mathcal{W}_{\textit{{EM}}}(\textsf{{{IC}}}_{\textit{{EM}}})$;

  * •

for each $f_{j}:p_{j}\pm\epsilon_{j}\in\Pi_{\mathit{EM}}$, create constraint:

$p_{j}-\epsilon_{j}\leq\sum_{w_{i}\in\mathcal{W}_{\textit{{EM}}}(\textsf{{{IC}}}_{\textit{{EM}}})\textit{
s.t.\ }w_{i}\models f_{j}}x_{i}\leq p_{j}+\epsilon_{j};$

  * •

finally, we also have a constraint:

$\sum_{w_{i}\in\mathcal{W}_{\textit{{EM}}}(\textsf{{{IC}}}_{\textit{{EM}}})}x_{i}=1.$

The objective is to minimize the function:

$\sum_{w_{i}\in\mathcal{W}_{\textit{{EM}}}(\textsf{{{IC}}}_{\textit{{EM}}})\textit{
s.t.\ }w_{i}\models q}x_{i}.$

We use the notation $\textsf{EP-LP-MIN}(\Pi_{\mathit{EM}},q)$ to refer to the
value of the objective function in the solution to the EM-LP-MIN constraints.

Let $\ell$ be the result of the process described in Definition 2.1. The next
step is to solve the linear program a second time, but instead maximizing the
objective function (we shall refer to this as EM-LP-MAX) – let $u$ be the
result of this operation. In [7], it is shown that $\epsilon=\frac{u-\ell}{2}$
and $p=\ell+\epsilon$ is the solution to the maximum entailment problem. We
note that although the above linear program has an exponential number of
variables in the worst case (i.e., no integrity constraints), the presence of
constraints has the potential to greatly reduce this space. Further, there are
also good heuristics (cf. [8, 10]) that have been shown to provide highly
accurate approximations with a reduced-size linear program.

###### Example 2.4

Consider KB $\Pi_{\mathit{EM}}^{\prime}$ from Example 2.3 and a set of ground
atoms restricted to those that appear in that program. Hence, we have:

$\displaystyle w_{1}$ $\displaystyle=$
$\displaystyle\\{\mathit{govCybLab}(\mathit{baja}),\mathit{cybCapAge}(\mathit{baja},5),$
$\displaystyle\mathit{mseTT}(\mathit{baja},2)\\}$ $\displaystyle w_{2}$
$\displaystyle=$
$\displaystyle\\{\mathit{govCybLab}(\mathit{baja}),\mathit{cybCapAge}(\mathit{baja},5)\\}$
$\displaystyle w_{3}$ $\displaystyle=$
$\displaystyle\\{\mathit{govCybLab}(\mathit{baja}),\mathit{mseTT}(\mathit{baja},2)\\}$
$\displaystyle w_{4}$ $\displaystyle=$
$\displaystyle\\{\mathit{cybCapAge}(\mathit{baja},5),\mathit{mseTT}(\mathit{baja},2)\\}$
$\displaystyle w_{5}$ $\displaystyle=$
$\displaystyle\\{\mathit{cybCapAge}(\mathit{baja},5)\\}$ $\displaystyle w_{6}$
$\displaystyle=$ $\displaystyle\\{\mathit{govCybLab}(\mathit{baja})\\}$
$\displaystyle w_{7}$ $\displaystyle=$
$\displaystyle\\{\mathit{mseTT}(\mathit{baja},2)\\}$ $\displaystyle w_{8}$
$\displaystyle=$ $\displaystyle\emptyset$

and suppose we wish to compute the probability for formula:

$q=\mathit{govCybLab}(\mathit{baja})\vee\mathit{mseTT}(\mathit{baja},2).$

For each formula in $\Pi_{\mathit{EM}}$ we have a constraint, and for each
world above we have a variable. An objective function is created based on the
worlds that satisfy the query formula (here, worlds $w_{1}$–$w_{4}$, $w_{6}$,
$w_{7}$). Hence, $\textsf{EP-LP-MIN}(\Pi_{\mathit{EM}}^{\prime},q)$ can be
written as:

$\displaystyle\max$ $\displaystyle x_{1}+x_{2}+x_{3}+x_{4}+x_{6}+x_{7}$
$\displaystyle\mathit{w.r.t.:}$ $\displaystyle 0.7\leq$ $\displaystyle
x_{1}+x_{2}+x_{3}+x_{6}$ $\displaystyle\leq 0.9$ $\displaystyle 0.1\leq$
$\displaystyle x_{1}+x_{2}+x_{4}+x_{5}$ $\displaystyle\leq 0.3$ $\displaystyle
0.8\leq$ $\displaystyle x_{1}+x_{3}+x_{4}+x_{7}$ $\displaystyle\leq 1$
$\displaystyle x_{1}+x_{2}+x_{3}+x_{4}+x_{5}+x_{6}+x_{7}+x_{8}$
$\displaystyle=1$

We can now solve $\textsf{EP-LP-MAX}(\Pi_{\mathit{EM}}^{\prime},q)$ and
$\textsf{EP-LP-MIN}(\Pi_{\mathit{EM}}^{\prime},q)$ to get solution $0.9\pm
0.1$. $\blacksquare$

###  2.2 Analytical Model

For the analytical model (AM), we choose a structured argumentation framework
[11] due to several characteristics that make such frameworks highly
applicable to cyber-warfare domains. Unlike the EM, which describes
probabilistic information about the state of the real world, the AM must allow
for competing ideas – it must be able to represent contradictory information.
The algorithmic approach allows for the creation of arguments based on the AM
that may “compete” with each other to describe who conducted a given cyber-
operation. In this competition – known as a dialectical process – one argument
may defeat another based on a comparison criterion that determines the
prevailing argument. Resulting from this process, the InCA framework will
determine arguments that are warranted (those that are not _defeated_ by other
arguments) thereby providing a suitable explanation for a given cyber-
operation.

The transparency provided by the system can allow analysts to identify
potentially incorrect input information and fine-tune the models or,
alternatively, collect more information. In short, argumentation-based
reasoning has been studied as a natural way to manage a set of inconsistent
information – it is the way humans settle disputes. As we will see, another
desirable characteristic of (structured) argumentation frameworks is that,
once a conclusion is reached, we are left with an explanation of how we
arrived at it and information about why a given argument is warranted; this is
very important information for analysts to have. In this section, we recall
some preliminaries of the underlying argumentation framework used, and then
introduce the analytical model (AM).

#### Defeasible Logic Programming with Presumptions

DeLP with Presumptions (PreDeLP) [12] is a formalism combining Logic
Programming with Defeasible Argumentation. We now briefly recall the basics of
PreDeLP; we refer the reader to [13, 12] for the complete presentation. The
formalism contains several different constructs: facts, presumptions, strict
rules, and defeasible rules. Facts are statements about the analysis that can
always be considered to be true, while presumptions are statements that may or
may not be true. Strict rules specify logical consequences of a set of facts
or presumptions (similar to an implication, though not the same) that must
always occur, while defeasible rules specify logical consequences that may be
assumed to be true when no contradicting information is present. These
constructs are used in the construction of _arguments_ , and are part of a
PreDeLP program, which is a set of facts, strict rules, presumptions, and
defeasible rules. Formally, we use the notation
$\Pi_{\mathit{AM}}=(\mbox{$\Theta$},\mbox{$\Omega$},\mbox{$\Phi$},\mbox{$\Delta$})$
to denote a PreDeLP program, where $\Omega$ is the set of strict rules,
$\Theta$ is the set of facts, $\Delta$ is the set of defeasible rules, and
$\Phi$ is the set of presumptions. In Figure 3, we provide an example
$\Pi_{\mathit{AM}}$. We now describe each of these constructs in detail.

Facts ($\Theta$) are ground literals representing atomic information or its
negation, using strong negation “$\neg$”. Note that all of the literals in our
framework must be formed with a predicate from the set
$\textsf{{{P}}}_{\textit{{AM}}}$. Note that information in this form cannot be
contradicted.

Strict Rules ($\Omega$) represent non-defeasible cause-and-effect information
that resembles an implication (though the semantics is different since the
contrapositive does not hold) and are of the form $L_{0}\\!\leftarrow
L_{1},\ldots,L_{n}$, where $L_{0}$ is a ground literal and $\\{L_{i}\\}_{i>0}$
is a set of ground literals.

Presumptions ($\Phi$) are ground literals of the same form as facts, except
that they are not taken as being true but rather defeasible, which means that
they can be contradicted. Presumptions are denoted in the same manner as
facts, except that the symbol –$\prec$ is added. While any literal can be used
as a presumption in InCA, we specifically require all literals created with
the predicate $\mathit{condOp}$ to be defeasible.

Defeasible Rules ($\Delta$) represent tentative knowledge that can be used if
nothing can be posed against it. Just as presumptions are the defeasible
counterpart of facts, defeasible rules are the defeasible counterpart of
strict rules. They are of the form $L_{0}\;{\raise
1.5pt\hbox{\tiny\mbox{\bf--\raise 0.1185pt\hbox{$\prec$}
}}}L_{1},\ldots,L_{n}$, where $L_{0}$ is a ground literal and
$\\{L_{i}\\}_{i>0}$ is a set of ground literals. Note that with both strict
and defeasible rules, strong negation is allowed in the head of rules, and
hence may be used to represent contradictory knowledge.

Even though the above constructs are ground, we allow for schematic versions
with variables that are used to represent sets of ground rules. We denote
variables with strings starting with an uppercase letter; Figure 4 shows a
non-ground example.

When a cyber-operation occurs, InCA must derive arguments as to who could have
potentially conducted the action. Derivation follows the same mechanism of
Logic Programming [14]. Since rule heads can contain strong negation, it is
possible to defeasibly derive contradictory literals from a program. For the
treatment of contradictory knowledge, PreDeLP incorporates a defeasible
argumentation formalism that allows the identification of the pieces of
knowledge that are in conflict, and through the previously mentioned
_dialectical process_ decides which information prevails as warranted.

$\mbox{$\Theta$}:$ ${\theta}_{1a}=$
$\mathit{evidOf}(\mathit{baja},\mathit{worm123})$ ${\theta}_{1b}=$
$\mathit{evidOf}(\mathit{mojave},\mathit{worm123})$ ${\theta}_{2}=$
$\mathit{motiv}(\mathit{baja},\mathit{krasnovia})$ $\mbox{$\Omega$}:$
${\omega}_{1a}=$
$\neg\mathit{condOp}(\mathit{baja},\mathit{worm123})\leftarrow$
$\mathit{condOp}(\mathit{mojave},\mathit{worm123})$ ${\omega}_{1b}=$
$\neg\mathit{condOp}(\mathit{mojave},\mathit{worm123})\leftarrow$
$\mathit{condOp}(\mathit{baja},\mathit{worm123})$ ${\omega}_{2a}=$
$\mathit{condOp}(\mathit{baja},\mathit{worm123})\leftarrow$
$\mathit{evidOf}(\mathit{baja},\mathit{worm123}),$
$\mathit{isCap}(\mathit{baja},\mathit{worm123}),$
$\mathit{motiv}(\mathit{baja},\mathit{krasnovia}),$
$\mathit{tgt}(\mathit{krasnovia},\mathit{worm123})$ ${\omega}_{2b}=$
$\mathit{condOp}(\mathit{mojave},\mathit{worm123})\leftarrow$
$\mathit{evidOf}(\mathit{mojave},\mathit{worm123}),$
$\mathit{isCap}(\mathit{mojave},\mathit{worm123}),$
$\mathit{motiv}(\mathit{mojave},\mathit{krasnovia}),$
$\mathit{tgt}(\mathit{krasnovia},\mathit{worm123})$ $\mbox{$\Phi$}:$
${{\phi}}_{1}=$ $\mathit{hasMseInvest}(\mathit{baja})\;{\raise
1.5pt\hbox{\tiny\mbox{\bf--\raise 0.1185pt\hbox{$\prec$} }}}$ ${{\phi}}_{2}=$
$\mathit{tgt}(\mathit{krasnovia},\mathit{worm123})\;{\raise
1.5pt\hbox{\tiny\mbox{\bf--\raise 0.1185pt\hbox{$\prec$} }}}$ ${{\phi}}_{3}=$
$\neg\mathit{expCw}(\mathit{baja})\;{\raise 1.5pt\hbox{\tiny\mbox{\bf--\raise
0.1185pt\hbox{$\prec$} }}}$ $\mbox{$\Delta$}:$ ${{\delta}}_{1a}=$
$\mathit{condOp}(\mathit{baja},\mathit{worm123})\;{\raise
1.5pt\hbox{\tiny\mbox{\bf--\raise 0.1185pt\hbox{$\prec$} }}}$
$\mathit{evidOf}(\mathit{baja},\mathit{worm123})$ ${{\delta}}_{1b}=$
$\mathit{condOp}(\mathit{mojave},\mathit{worm123})\;{\raise
1.5pt\hbox{\tiny\mbox{\bf--\raise 0.1185pt\hbox{$\prec$} }}}$
$\mathit{evidOf}(\mathit{mojave},\mathit{worm123})$ ${{\delta}}_{2}=$
$\mathit{condOp}(\mathit{baja},\mathit{worm123})\;{\raise
1.5pt\hbox{\tiny\mbox{\bf--\raise 0.1185pt\hbox{$\prec$} }}}$
$\mathit{isCap}(\mathit{baja},\mathit{worm123})$ ${{\delta}}_{3}=$
$\mathit{condOp}(\mathit{baja},\mathit{worm123})\;{\raise
1.5pt\hbox{\tiny\mbox{\bf--\raise 0.1185pt\hbox{$\prec$} }}}$
$\mathit{motiv}(\mathit{baja},\mathit{krasnovia}),$
$\mathit{tgt}(\mathit{krasnovia},\mathit{worm123})$ ${{\delta}}_{4}=$
$\mathit{isCap}(\mathit{baja},\mathit{worm123})\;{\raise
1.5pt\hbox{\tiny\mbox{\bf--\raise 0.1185pt\hbox{$\prec$} }}}$
$\mathit{hasMseInvest}(\mathit{baja})$ ${{\delta}}_{5a}=$
$\neg\mathit{isCap}(\mathit{baja},\mathit{worm123})\;{\raise
1.5pt\hbox{\tiny\mbox{\bf--\raise 0.1185pt\hbox{$\prec$}
}}}\neg\mathit{expCw}(\mathit{baja})$ ${{\delta}}_{5b}=$
$\neg\mathit{isCap}(\mathit{mojave},\mathit{worm123})\;{\raise
1.5pt\hbox{\tiny\mbox{\bf--\raise 0.1185pt\hbox{$\prec$} }}}$
$\neg\mathit{expCw}(\mathit{mojave})$

Figure 3: A ground argumentation framework.

$\mbox{$\Theta$}:$ ${\theta}_{1}=$
$\mathit{evidOf}(\mathit{baja},\mathit{worm123})$ ${\theta}_{2}=$
$\mathit{motiv}(\mathit{baja},\mathit{krasnovia})$ $\mbox{$\Omega$}:$
${\omega}_{1}=$
$\neg\mathit{condOp}(X,O)\leftarrow\mathit{condOp}(X^{\prime},O),$ $X\neq
X^{\prime}$ ${\omega}_{2}=$
$\mathit{condOp}(X,O)\leftarrow\mathit{evidOf}(X,O),$
$\mathit{isCap}(X,O),\mathit{motiv}(X,X^{\prime}),$
$\mathit{tgt}(X^{\prime},O),X\neq X^{\prime}$ $\mbox{$\Phi$}:$ ${{\phi}}_{1}=$
$\mathit{hasMseInvest}(\mathit{baja})\;{\raise
1.5pt\hbox{\tiny\mbox{\bf--\raise 0.1185pt\hbox{$\prec$} }}}$ ${{\phi}}_{2}=$
$\mathit{tgt}(\mathit{krasnovia},\mathit{worm123})\;{\raise
1.5pt\hbox{\tiny\mbox{\bf--\raise 0.1185pt\hbox{$\prec$} }}}$ ${{\phi}}_{3}=$
$\neg\mathit{expCw}(\mathit{baja})\;{\raise 1.5pt\hbox{\tiny\mbox{\bf--\raise
0.1185pt\hbox{$\prec$} }}}$ $\mbox{$\Delta$}:$ ${{\delta}}_{1}=$
$\mathit{condOp}(X,O)\;{\raise 1.5pt\hbox{\tiny\mbox{\bf--\raise
0.1185pt\hbox{$\prec$} }}}\mathit{evidOf}(X,O)$ ${{\delta}}_{2}=$
$\mathit{condOp}(X,O)\;{\raise 1.5pt\hbox{\tiny\mbox{\bf--\raise
0.1185pt\hbox{$\prec$} }}}\mathit{isCap}(X,O)$ ${{\delta}}_{3}=$
$\mathit{condOp}(X,O)\;{\raise 1.5pt\hbox{\tiny\mbox{\bf--\raise
0.1185pt\hbox{$\prec$}
}}}\mathit{motiv}(X,X^{\prime}),\mathit{tgt}(X^{\prime},O)$ ${{\delta}}_{4}=$
$\mathit{isCap}(X,O)\;{\raise 1.5pt\hbox{\tiny\mbox{\bf--\raise
0.1185pt\hbox{$\prec$} }}}\mathit{hasMseInvest}(X)$ ${{\delta}}_{5}=$
$\neg\mathit{isCap}(X,O)\;{\raise 1.5pt\hbox{\tiny\mbox{\bf--\raise
0.1185pt\hbox{$\prec$} }}}\neg\mathit{expCw}(X)$

Figure 4: A non-ground argumentation framework.

This dialectical process involves the construction and evaluation of arguments
that either support or interfere with a given query, building a _dialectical
tree_ in the process. Formally, we have:

######  Definition 2.2 (Argument)

An _argument_ $\langle\mbox{$\mathcal{A}$},L\rangle$ for a literal $L$ is a
pair of the literal and a (possibly empty) set of the EM
($\mbox{$\mathcal{A}$}\subseteq\Pi_{\mathit{AM}}$) that provides a minimal
proof for $L$ meeting the requirements: (1.) $L$ is defeasibly derived from
$\mathcal{A}$, (2.)
$\mbox{$\Omega$}\cup\mbox{$\Theta$}\cup\mbox{$\mathcal{A}$}$ is not
contradictory, and (3.) $\mathcal{A}$ is a minimal subset of
$\mbox{$\Delta$}\cup\mbox{$\Phi$}$ satisfying 1 and 2, denoted
$\langle\mbox{$\mathcal{A}$},L\rangle$.

Literal $L$ is called the conclusion supported by the argument, and
$\mathcal{A}$ is the _support_ of the argument. An argument
$\langle\mathcal{B},L\rangle$ is a subargument of
$\langle\mathcal{A},L^{\prime}\rangle$ iff $\mathcal{B}\subseteq\mathcal{A}$.
An argument $\langle\mathcal{A},L\rangle$ is presumptive iff
$\mathcal{A}\cap\mbox{$\Phi$}$ is not empty. We will also use
$\mbox{$\Omega$}(\mathcal{A})=\mathcal{A}\cap\mbox{$\Omega$}$,
$\mbox{$\Theta$}(\mathcal{A})=\mathcal{A}\cap\mbox{$\Theta$}$,
$\mbox{$\Delta$}(\mathcal{A})=\mathcal{A}\cap\mbox{$\Delta$}$, and
$\mbox{$\Phi$}(\mathcal{A})=\mathcal{A}\cap\mbox{$\Phi$}$.

Note that our definition differs slightly from that of [15] where DeLP is
introduced, as we include strict rules and facts as part of the argument. The
reason for this will become clear in Section 3. Arguments for our scenario are
shown in the following example.

###### Example 2.5

Figure 5 shows example arguments based on the knowledge base from Figure 3.
Note that the following relationship exists:

>
> $\langle\mathcal{A}_{5},\mathit{isCap}(\mathit{baja},\mathit{worm123})\rangle$
> is a sub-argument of
>
> $\langle\mathcal{A}_{2},\mathit{condOp}(\mathit{baja},\mathit{worm123})\rangle$
> and
>
> $\langle\mathcal{A}_{3},\mathit{condOp}(\mathit{baja},\mathit{worm123})\rangle$.
> $\blacksquare$

$\langle\mathcal{A}_{1},\mathit{condOp}(\mathit{baja},\mathit{worm123})\rangle$
$\mathcal{A}_{1}=\\{{\theta}_{1a},{{\delta}}_{1a}\\}$
$\langle\mathcal{A}_{2},\mathit{condOp}(\mathit{baja},\mathit{worm123})\rangle$
$\mathcal{A}_{2}=\\{{{\phi}}_{1},{{\phi}}_{2},{{\delta}}_{4},{\omega}_{2a},$
${\theta}_{1a},{\theta}_{2}\\}$
$\langle\mathcal{A}_{3},\mathit{condOp}(\mathit{baja},\mathit{worm123})\rangle$
$\mathcal{A}_{3}=\\{{{\phi}}_{1},{{\delta}}_{2},{{\delta}}_{4}\\}$
$\langle\mathcal{A}_{4},\mathit{condOp}(\mathit{baja},\mathit{worm123})\rangle$
$\mathcal{A}_{4}=\\{{{\phi}}_{2},{{\delta}}_{3},{\theta}_{2}\\}$
$\langle\mathcal{A}_{5},\mathit{isCap}(\mathit{baja},\mathit{worm123})\rangle$
$\mathcal{A}_{5}=\\{{{\phi}}_{1},{{\delta}}_{4}\\}$
$\langle\mathcal{A}_{6},\neg\mathit{condOp}(\mathit{baja},\mathit{worm123})\rangle$
$\mathcal{A}_{6}=\\{{{\delta}}_{1b},{\theta}_{1b},{\omega}_{1a}\\}$
$\langle\mathcal{A}_{7},\neg\mathit{isCap}(\mathit{baja},\mathit{worm123})\rangle$
$\mathcal{A}_{7}=\\{{{\phi}}_{3},{{\delta}}_{5a}\\}$

Figure 5: Example ground arguments from Figure 3.

Given argument $\langle\mathcal{A}_{1},L_{1}\rangle$, counter-arguments are
arguments that contradict it. Argument $\langle\mathcal{A}_{2},L_{2}\rangle$
counterargues or attacks $\langle\mathcal{A}_{1},L_{1}\rangle$ literal
$L^{\prime}$ iff there exists a subargument
$\langle\mathcal{A},L^{\prime\prime}\rangle$ of
$\langle\mathcal{A}_{1},L_{1}\rangle$ s.t. set
$\mbox{$\Omega$}(\mathcal{A}_{1})\cup\mbox{$\Omega$}(\mathcal{A}_{2})\cup\mbox{$\Theta$}(\mathcal{A}_{1})\cup\mbox{$\Theta$}(\mathcal{A}_{2})\cup\\{L_{2},L^{\prime\prime}\\}$
is contradictory.

###### Example 2.6

Consider the arguments from Example 2.5. The following are some of the attack
relationships between them: $\mathcal{A}_{1}$, $\mathcal{A}_{2}$,
$\mathcal{A}_{3}$, and $\mathcal{A}_{4}$ all attack $\mathcal{A}_{6}$;
$\mathcal{A}_{5}$ attacks $\mathcal{A}_{7}$; and $\mathcal{A}_{7}$ attacks
$\mathcal{A}_{2}$. $\blacksquare$

A proper defeater of an argument $\langle A,L\rangle$ is a counter-argument
that – by some criterion – is considered to be better than $\langle
A,L\rangle$; if the two are incomparable according to this criterion, the
counterargument is said to be a blocking defeater. An important characteristic
of PreDeLP is that the argument comparison criterion is modular, and thus the
most appropriate criterion for the domain that is being represented can be
selected; the default criterion used in classical defeasible logic programming
(from which PreDeLP is derived) is _generalized specificity_ [16], though an
extension of this criterion is required for arguments using presumptions [12].
We briefly recall this criterion next – the first definition is for
generalized specificity, which is subsequently used in the definition of
presumption-enabled specificity.

###### Definition 2.3

Let
$\mbox{$\Pi_{\mathit{AM}}$}=(\mbox{$\Theta$},\mbox{$\Omega$},\mbox{$\Phi$},\mbox{$\Delta$})$
be a PreDeLP program and let $\mathcal{F}$ be the set of all literals that
have a defeasible derivation from $\Pi_{\mathit{AM}}$. An argument
$\langle\mathcal{A}_{1},L_{1}\rangle$ is _preferred to_
$\langle\mathcal{A}_{2},L_{2}\rangle$, denoted with
$\mathcal{A}_{1}\succ_{PS}\mathcal{A}_{2}$ iff the two following conditions
hold:

  1. 1.

For all $H\subseteq\mathcal{F}$,
$\mbox{$\Omega$}(\mathcal{A}_{1})\cup\mbox{$\Omega$}(\mathcal{A}_{2})\cup H$
is non-contradictory: if there is a derivation for $L_{1}$ from
$\mbox{$\Omega$}(\mathcal{A}_{2})\cup\mbox{$\Omega$}(\mathcal{A}_{1})\cup\mbox{$\Delta$}(\mathcal{A}_{1})\cup
H$, and there is no derivation for $L_{1}$ from
$\mbox{$\Omega$}(\mathcal{A}_{1})\cup\mbox{$\Omega$}(\mathcal{A}_{2})\cup H$,
then there is a derivation for $L_{2}$ from
$\mbox{$\Omega$}(\mathcal{A}_{1})\cup\mbox{$\Omega$}(\mathcal{A}_{2})\cup\mbox{$\Delta$}(\mathcal{A}_{2})\cup
H$.

  2. 2.

There is at least one set $H^{\prime}\subseteq\mathcal{F}$,
$\mbox{$\Omega$}(\mathcal{A}_{1})\cup\mbox{$\Omega$}(\mathcal{A}_{2})\cup
H^{\prime}$ is non-contradictory, such that there is a derivation for $L_{2}$
from $\mbox{$\Omega$}(\mathcal{A}_{1})\cup\mbox{$\Omega$}(\mathcal{A}_{2})\cup
H^{\prime}\cup\mbox{$\Delta$}(\mathcal{A}_{2})$, there is no derivation for
$L_{2}$ from
$\mbox{$\Omega$}(\mathcal{A}_{1})\cup\mbox{$\Omega$}(\mathcal{A}_{2})\cup
H^{\prime}$, and there is no derivation for $L_{1}$ from
$\mbox{$\Omega$}(\mathcal{A}_{1})\cup\mbox{$\Omega$}(\mathcal{A}_{2})\cup
H^{\prime}\cup\mbox{$\Delta$}(\mathcal{A}_{1})$.

Intuitively, the principle of specificity says that, in the presence of two
conflicting lines of argument about a proposition, the one that uses more of
the available information is more convincing. A classic example involves a
bird, Tweety, and arguments stating that it both flies (because it is a bird)
and doesn’t fly (because it is a penguin). The latter argument uses more
information about Tweety – it is more specific – and is thus the stronger of
the two.

######  Definition 2.4 ([12])

Let
$\mbox{$\Pi_{\mathit{AM}}$}=(\mbox{$\Theta$},\mbox{$\Omega$},\mbox{$\Phi$},\mbox{$\Delta$})$
be a PreDeLP program. An argument $\langle\mathcal{A}_{1},L_{1}\rangle$ is
_preferred to_ $\langle\mathcal{A}_{2},L_{2}\rangle$, denoted with
$\mathcal{A}_{1}\succ\mathcal{A}_{2}$ iff any of the following conditions
hold:

  1. 1.

$\langle\mathcal{A}_{1},L_{1}\rangle$ and
$\langle\mathcal{A}_{2},L_{2}\rangle$ are both factual arguments and
$\langle\mathcal{A}_{1},L_{1}\rangle\succ_{PS}\langle\mathcal{A}_{2},L_{2}\rangle$.

  2. 2.

$\langle\mathcal{A}_{1},L_{1}\rangle$ is a factual argument and
$\langle\mathcal{A}_{2},L_{2}\rangle$ is a presumptive argument.

  3. 3.

$\langle\mathcal{A}_{1},L_{1}\rangle$ and
$\langle\mathcal{A}_{2},L_{2}\rangle$ are presumptive arguments, and

    1. (a)

$\neg(\mbox{$\Phi$}(\mathcal{A}_{1})\subseteq\mbox{$\Phi$}(\mathcal{A}_{2}))$,
or

    2. (b)

$\mbox{$\Phi$}(\mathcal{A}_{1})=\mbox{$\Phi$}(\mathcal{A}_{2})$ and
$\langle\mathcal{A}_{1},L_{1}\rangle\succ_{PS}\langle\mathcal{A}_{2},L_{2}\rangle$.

Generally, if $\mathcal{A},\mathcal{B}$ are arguments with rules $X$ and $Y$,
resp., and $X\subset Y$, then $\mathcal{A}$ is stronger than $\mathcal{B}$.
This also holds when $\mathcal{A}$ and $\mathcal{B}$ use presumptions $P_{1}$
and $P_{2}$, resp., and $P_{1}\subset P_{2}$.

###### Example 2.7

The following are relationships between arguments from Example 2.5, based on
Definitions 2.3 and 2.4:

$\mathcal{A}_{1}$ and $\mathcal{A}_{6}$ are incomparable (blocking defeaters);
$\mathcal{A}_{6}\succ\mathcal{A}_{2}$, and thus $\mathcal{A}_{6}$ defeats
$\mathcal{A}_{2}$;
$\mathcal{A}_{6}\succ\mathcal{A}_{3}$, and thus $\mathcal{A}_{6}$ defeats
$\mathcal{A}_{3}$;
$\mathcal{A}_{6}\succ\mathcal{A}_{4}$, and thus $\mathcal{A}_{6}$ defeats
$\mathcal{A}_{4}$;
$\mathcal{A}_{5}$ and $\mathcal{A}_{7}$ are incomparable (blocking defeaters).
$\blacksquare$

A sequence of arguments called an _argumentation line_ thus arises from this
attack relation, where each argument defeats its predecessor. To avoid
undesirable sequences, that may represent circular or fallacious argumentation
lines, in DeLP an _argumentation line_ is _acceptable_ if it satisfies certain
constraints (see [13]). A literal $L$ is _warranted_ if there exists a non-
defeated argument $\mathcal{A}$ supporting $L$.

Clearly, there can be more than one defeater for a particular argument
$\langle\mathcal{A},L\rangle$. Therefore, many acceptable argumentation lines
could arise from $\langle\mathcal{A},L\rangle$, leading to a tree structure.
The tree is built from the set of all argumentation lines rooted in the
initial argument. In a dialectical tree, every node (except the root)
represents a defeater of its parent, and leaves correspond to undefeated
arguments. Each path from the root to a leaf corresponds to a different
acceptable argumentation line. A dialectical tree provides a structure for
considering all the possible acceptable argumentation lines that can be
generated for deciding whether an argument is defeated. We call this tree
_dialectical_ because it represents an exhaustive dialectical111In the sense
of providing reasons for and against a position. analysis for the argument in
its root. For argument $\langle\mathcal{A},L\rangle$, we denote its
dialectical tree with
${\mathcal{T}}({\small\langle\mbox{$\mathcal{A}$},L\rangle})$.

Given a literal $L$ and an argument $\langle\mbox{$\mathcal{A}$},L\rangle$, in
order to decide whether or not a literal $L$ is warranted, every node in the
dialectical tree ${\mathcal{T}}({\small\langle\mbox{$\mathcal{A}$},L\rangle})$
is recursively marked as “D” (_defeated_) or “U” (_undefeated_), obtaining a
marked dialectical tree
${\mathcal{T}^{*}}({\small\langle\mbox{$\mathcal{A}$},L\rangle})$ where:

  * •

All leaves in
${\mathcal{T}^{*}}({\small\langle\mbox{$\mathcal{A}$},L\rangle})$ are marked
as “U”s, and

  * •

Let $\langle\mbox{${\mathcal{B}}$},q\rangle$ be an inner node of
${\mathcal{T}^{*}}({\small\langle\mbox{$\mathcal{A}$},L\rangle})$. Then,
$\langle\mbox{${\mathcal{B}}$},q\rangle$ will be marked as “U” iff every child
of $\langle\mbox{${\mathcal{B}}$},q\rangle$ is marked as “D”. Node
$\langle\mbox{${\mathcal{B}}$},q\rangle$ will be marked as “D” iff it has at
least a child marked as “U”.

Given argument $\langle\mbox{$\mathcal{A}$},L\rangle$ over
$\Pi_{\mathit{AM}}$, if the root of
${\mathcal{T}^{*}}({\small\langle\mbox{$\mathcal{A}$},L\rangle})$ is marked
“U”, then
${\mathcal{T}^{*}}({\small\mbox{$\langle\mbox{$\mathcal{A}$},h\rangle$}})$
_warrants_ $L$ and that $L$ is _warranted_ from $\Pi_{\mathit{AM}}$.
(Warranted arguments correspond to those in the grounded extension of a Dung
argumentation system [17].)

We can then extend the idea of a dialectical tree to a dialectical forest. For
a given literal $L$, a dialectical forest $\mathcal{F}(L)$ consists of the set
of dialectical trees for all arguments for $L$. We shall denote a marked
dialectical forest, the set of all marked dialectical trees for arguments for
$L$, as $\mathcal{F}^{*}(L)$. Hence, for a literal $L$, we say it is warranted
if there is at least one argument for that literal in the dialectical forest
$\mathcal{F}^{*}(L)$ that is labeled “U”, not warranted if there is at least
one argument for literal $\neg L$ in the forest $\mathcal{F}^{*}(\neg L)$ that
is labeled “U”, and undecided otherwise.

##  3 The InCA Framework

Having defined our environmental and analytical models
($\Pi_{\mathit{EM}},\Pi_{\mathit{AM}}$ respectively), we now define how the
two relate, which allows us to complete the definition of our InCA framework.

The key intuition here is that given a $\Pi_{\mathit{AM}}$, every element of
$\mbox{$\Omega$}\cup\mbox{$\Theta$}\cup\mbox{$\mbox{$\Delta$}\cup\mbox{$\Phi$}$}$
might only hold in certain worlds in the set $\mathcal{W}_{\textit{{EM}}}$ –
that is, worlds specified by the environment model. As formulas over the
environmental atoms in set $\textsf{{{G}}}_{\textit{{EM}}}$ specify subsets of
$\mathcal{W}_{\textit{{EM}}}$ (i.e., the worlds that satisfy them), we can use
these formulas to identify the conditions under which a component of
$\mbox{$\Omega$}\cup\mbox{$\Theta$}\cup\mbox{$\mbox{$\Delta$}\cup\mbox{$\Phi$}$}$
can be true. Recall that we use the notation $formula_{EM}$ to denote the set
of all possible formulas over $\textsf{{{G}}}_{\textit{{EM}}}$. Therefore, it
makes sense to associate elements of
$\mbox{$\Omega$}\cup\mbox{$\Theta$}\cup\mbox{$\mbox{$\Delta$}\cup\mbox{$\Phi$}$}$
with a formula from $formula_{EM}$. In doing so, we can in turn compute the
probabilities of subsets of
$\mbox{$\Omega$}\cup\mbox{$\Theta$}\cup\mbox{$\mbox{$\Delta$}\cup\mbox{$\Phi$}$}$
using the information contained in $\Pi_{\mathit{EM}}$, which we shall
describe shortly. We first introduce the notion of annotation function, which
associates elements of
$\mbox{$\Omega$}\cup\mbox{$\Theta$}\cup\mbox{$\mbox{$\Delta$}\cup\mbox{$\Phi$}$}$
with elements of $formula_{EM}$.

We also note that, by using the annotation function (see Figure 6), we may
have certain statements that appear as both facts and presumptions (likewise
for strict and defeasible rules). However, these constructs would have
different annotations, and thus be applicable in different worlds. Suppose we
added the following presumptions to our running example:

  * ${{\phi}}_{3}=\mathit{evidOf}(X,O)\;{\raise 1.5pt\hbox{\tiny\mbox{\bf--\raise 0.1185pt\hbox{$\prec$} }}}$, and

  * ${{\phi}}_{4}=\mathit{motiv}(X,X^{\prime})\;{\raise 1.5pt\hbox{\tiny\mbox{\bf--\raise 0.1185pt\hbox{$\prec$} }}}$.

Note that these presumptions are constructed using the same formulas as facts
${\theta}_{1},{\theta}_{2}$. Suppose we extend $\mathit{af}$ as follows:

$\displaystyle\mathit{af}({{\phi}}_{3})$ $\displaystyle=$
$\displaystyle\mathit{malwInOp}(M,O)\wedge\mathit{malwareRel}(M,M^{\prime})$
$\displaystyle\wedge\mathit{mwHint}(M^{\prime},X)$
$\displaystyle\mathit{af}({{\phi}}_{4})$ $\displaystyle=$
$\displaystyle\mathit{inLgConf}(Y,X^{\prime})\wedge\mathit{cooper}(X,Y)$

So, for instance, unlike ${\theta}_{1}$, ${{\phi}}_{3}$ can potentially be
true in any world of the form:

$\\{\mathit{malwInOp}(M,O),\mathit{malwareRel}(M,M^{\prime}),\mathit{mwHint}(M^{\prime},X)\\}$

while ${\theta}_{1}$ cannot be considered in any those worlds.

With the annotation function, we now have all the components to formally
define an InCA framework.

######  Definition 3.1 (InCA Framework)

Given environmental model $\Pi_{\mathit{EM}}$, analytical model
$\Pi_{\mathit{AM}}$, and annotation function $\mathit{af}$,
$\mathcal{I}=(\Pi_{\mathit{EM}},\Pi_{\mathit{AM}},\mathit{af})$ is an InCA
framework.

$\mathit{af}({\theta}_{1})=$
$\mathit{origIP}(\mathit{worm123},\mathit{baja})\vee$
$\big{(}\mathit{malwInOp}(\mathit{worm123},o)\wedge$
$\big{(}\mathit{mwHint}(\mathit{worm123},\mathit{baja})\vee$
$(\mathit{compilLang}(\mathit{worm123},c)\wedge$
$\mathit{nativLang}(\mathit{baja},c))\big{)}\big{)}$
$\mathit{af}({\theta}_{2})=$
$\mathit{inLgConf}(\mathit{baja},\mathit{krasnovia})$
$\mathit{af}({\omega}_{1})=$ True $\mathit{af}({\omega}_{2})=$ True
$\mathit{af}({{\phi}}_{1})=$
$\mathit{mseTT}(\mathit{baja},2)\vee\mathit{govCybLab}(\mathit{baja})$
$\mathit{af}({{\phi}}_{2})=$
$\mathit{malwInOp}(\mathit{worm123},o^{\prime})\wedge$
$\mathit{infGovSys}(\mathit{krasnovia},\mathit{worm123})$
$\mathit{af}({{\phi}}_{3})=$ $\mathit{cybCapAge}(\mathit{baja},5)$
$\mathit{af}({{\delta}}_{1})=$ True $\mathit{af}({{\delta}}_{2})=$ True
$\mathit{af}({{\delta}}_{3})=$ True $\mathit{af}({{\delta}}_{4})=$ True
$\mathit{af}({{\delta}}_{5})=$ True

Figure 6: Example annotation function.

Given the setup described above, we consider a world-based approach – the
defeat relationship among arguments will depend on the current state of the
world (based on the EM). Hence, we now define the status of an argument with
respect to a given world.

######  Definition 3.2 (Validity)

Given InCA framework
$\mathcal{I}=(\Pi_{\mathit{EM}},\Pi_{\mathit{AM}},\mathit{af})$, argument
$\langle\mathcal{A},L\rangle$ is valid w.r.t. world
$w\in\mathcal{W}_{\textit{{EM}}}$ iff $\forall
c\in\mathcal{A},w\models\mathit{af}(c)$.

In other words, an argument is valid with respect to $w$ if the rules, facts,
and presumptions in that argument are present in $w$ – the argument can then
be built from information that is available in that world. In this paper, we
extend the notion of validity to argumentation lines, dialectical trees, and
dialectical forests in the expected way (an argumentation line is valid w.r.t.
$w$ iff all arguments that comprise that line are valid w.r.t. $w$).

###### Example 3.1

Consider worlds $w_{1},\ldots,w_{8}$ from Example 2.4 along with the argument
$\langle\mathcal{A}_{5},\mathit{isCap}(\mathit{baja},\mathit{worm123})\rangle$
from Example 2.5. This argument is valid in worlds $w_{1}$–$w_{4}$, $w_{6}$,
and $w_{7}$. $\blacksquare$

We now extend the idea of a dialectical tree w.r.t. worlds – so, for a given
world $w\in\mathcal{W}_{\textit{{EM}}}$, the dialectical (resp., marked
dialectical) tree induced by $w$ is denoted by
$\mathcal{T}_{w}{\langle\mbox{$\mathcal{A}$},L\rangle}$ (resp.,
$\mathcal{T}^{*}_{w}{\langle\mbox{$\mathcal{A}$},L\rangle}$). We require that
all arguments and defeaters in these trees to be valid with respect to $w$.
Likewise, we extend the notion of dialectical forests in the same manner
(denoted with $\mathcal{F}_{w}(L)$ and $\mathcal{F}^{*}_{w}(L)$,
respectively). Based on these concepts we introduce the notion of warranting
scenario.

######  Definition 3.3 (Warranting Scenario)

Let $\mathcal{I}=$ $(\Pi_{\mathit{EM}},$ $\Pi_{\mathit{AM}},$ $\mathit{af})$
be an InCA framework and $L$ be a ground literal over
$\textsf{{{G}}}_{\textit{{AM}}}$; a world $w\in\mathcal{W}_{\textit{{EM}}}$ is
said to be a warranting scenario for $L$ (denoted $w\vdash_{\textsf{war}}L$)
iff there is a dialectical forest $\mathcal{F}^{*}_{w}(L)$ in which $L$ is
warranted and $\mathcal{F}^{*}_{w}(L)$ is valid w.r.t $w$.

###### Example 3.2

Following from Example 3.1, argument
$\langle\mathcal{A}_{5},\mathit{isCap}(\mathit{baja},\mathit{worm123})\rangle$
is warranted in worlds $w_{3}$, $w_{6}$, and $w_{7}$. $\blacksquare$

Hence, the set of worlds in the EM where a literal $L$ in the AM must be true
is exactly the set of warranting scenarios – these are the “necessary” worlds,
denoted:

$nec(L)=\\{w\in\mathcal{W}_{\textit{{EM}}}\;|\;(w\vdash_{\textsf{war}}L).\\}$

Now, the set of worlds in the EM where AM literal $L$ can be true is the
following – these are the “possible” worlds, denoted:

$poss(L)=\\{w\in\mathcal{W}_{\textit{{EM}}}\;|\;w\not\vdash_{\textsf{war}}\neg
L\\}.$

The following example illustrates these concepts.

###### Example 3.3

Following from Example 3.1:

$nec(\mathit{isCap}(\mathit{baja},\mathit{worm123}))=\\{w_{3},w_{6},w_{7}\\}$
and

$poss(\mathit{isCap}(\mathit{baja},\mathit{worm123}))=\\{w_{1},w_{2},w_{3},w_{4},w_{6},w_{7}\\}$.

$\blacksquare$

Hence, for a given InCA framework $\mathcal{I}$, if we are given a probability
distribution Pr over the worlds in the EM, then we can compute an upper and
lower bound on the probability of literal $L$ (denoted
$\textbf{{P}}_{L,\textsf{{Pr}},\mathcal{I}}$) as follows:

$\ell_{L,\textsf{{Pr}},\mathcal{I}}=\sum_{w\in nec(L)}\textsf{{Pr}}(w),$
$u_{L,\textsf{{Pr}},\mathcal{I}}=\sum_{w\in poss(L)}\textsf{{Pr}}(w),$

and

$\ell_{L,\textsf{{Pr}},\mathcal{I}}\leq\textbf{{P}}_{L,\textsf{{Pr}},\mathcal{I}}\leq
u_{L,\textsf{{Pr}},\mathcal{I}}.$

Now let us consider the computation of probability bounds on a literal when we
are given a knowledge base $\Pi_{\mathit{EM}}$ in the environmental model,
which is specified in $\mathcal{I}$, instead of a probability distribution
over all worlds. For a given world $w\in\mathcal{W}_{\textit{{EM}}}$, let
$for(w)=\big{(}\bigwedge_{a\in w}a\big{)}\wedge\big{(}\bigwedge_{a\notin
w}\neg a\big{)}$ – that is, a formula that is satisfied only by world $w$. Now
we can determine the upper and lower bounds on the probability of a literal
w.r.t. $\Pi_{\mathit{EM}}$ (denoted $\textbf{{P}}_{L,\mathcal{I}}$) as
follows:

$\ell_{L,\mathcal{I}}=\textsf{EP-LP-MIN}\left(\Pi_{\mathit{EM}},\bigvee_{w\in
nec(L)}for(w)\right),$ $u_{L,\mathcal{I}}=\textsf{EP-LP-
MAX}\left(\Pi_{\mathit{EM}},\bigvee_{w\in poss(L)}for(w)\right),$

and

$\ell_{L,\mathcal{I}}\leq\textbf{{P}}_{L,\mathcal{I}}\leq u_{L,\mathcal{I}}.$

Hence,
$\textbf{{P}}_{L,\mathcal{I}}=\left(\ell_{L,\mathcal{I}}+\frac{u_{L,\mathcal{I}}-\ell_{L,\mathcal{I}}}{2}\right)\pm\frac{u_{L,\mathcal{I}}-\ell_{L,\mathcal{I}}}{2}$.

###### Example 3.4

Following from Example 3.1, argument
$\langle\mathcal{A}_{5},\mathit{isCap}(\mathit{baja},\mathit{worm123})\rangle$,
we can compute
$\textbf{{P}}_{\mathit{isCap}(\mathit{baja},\mathit{worm123}),\mathcal{I}}$
(where $\mathcal{I}=(\Pi_{EM}^{\prime},\Pi_{AM},\mathit{af}))$. Note that for
the upper bound, the linear program we need to set up is as in Example 2.4.
For the lower bound, the objective function changes to: $\min
x_{3}+x_{6}+x_{7}$. From these linear constraints, we obtain:
$\textbf{{P}}_{\mathit{isCap}(\mathit{baja},\mathit{worm123}),\mathcal{I}}=0.75\pm
0.25.$ $\blacksquare$

##  4 Attribution Queries

We now have the necessary elements required to formally define the kind of
queries that correspond to the attribution problems studied in this paper.

###### Definition 4.1

Let $\mathcal{I}=(\Pi_{\mathit{EM}},\Pi_{\mathit{AM}},\mathit{af})$ be an InCA
framework, $\mathcal{S}\subseteq\textsf{{C}}_{act}$ (the set of “suspects”),
$\mathcal{O}\in\textsf{{C}}_{ops}$ (the “operation”), and
$\mathcal{E}\subseteq\textsf{{{G}}}_{\textit{{EM}}}$ (the “evidence”). An
actor $\textsf{A}\in\mathcal{S}$ is said to be a most probable suspect iff
there does not exist $\textsf{A}^{\prime}\in\mathcal{S}$ such that
$\textbf{{P}}_{\mathit{condOp}(\textsf{A}^{\prime},\mathcal{O}),\mathcal{I}^{\prime}}>\textbf{{P}}_{\mathit{condOp}(\textsf{A},\mathcal{O}),\mathcal{I}^{\prime}}$
where
$\mathcal{I}^{\prime}=(\Pi_{\mathit{EM}}\cup\Pi_{\mathcal{E}},\Pi_{\mathit{AM}},\mathit{af}^{\prime})$
with $\Pi_{\mathcal{E}}$ defined as $\bigcup_{c\in\mathcal{E}}\\{c:1\pm 0\\}$.

Given the above definition, we refer to
$Q=(\mathcal{I},\mathcal{S},\mathcal{O},\mathcal{E})$ as an attribution query,
and A as an answer to $Q$. We note that in the above definition, the items of
evidence are added to the environmental model with a probability of $1$. While
in general this may be the case, there are often instances in analysis of a
cyber-operation where the evidence may be true with some degree of
uncertainty. Allowing for probabilistic evidence is a simple extension to
Definition 4.1 that does not cause any changes to the results of this paper.

To understand how uncertain evidence can be present in a cyber-security
scenario, consider the following. In Symantec’s initial analysis of the
Stuxnet worm, they found the routine designed to attack the S7-417 logic
controller was incomplete, and hence would not function [18]. However,
industrial control system expert Ralph Langner claimed that the incomplete
code would run provided a missing data block is generated, which he thought
was possible [19]. In this case, though the code was incomplete, there was
clearly uncertainty regarding its usability. This situation provides a real-
world example of the need to compare arguments – in this case, in the worlds
where both arguments are valid, Langner’s argument would likely defeat
Symantec’s by generalized specificity (the outcome, of course, will depend on
the exact formalization of the two). Note that Langner was later vindicated by
the discovery of an older sample, Stuxnet 0.5, which generated the data
block.222http://www.symantec.com/connect/blogs/stuxnet-05-disrupting-uranium-
processing-natanz

InCA also allows for a variety of relevant scenarios to the attribution
problem. For instance, we can easily allow for the modeling of non-state
actors by extending the available constants – for example, traditional groups
such as Hezbollah, which has previously wielded its cyber-warfare capabilities
in operations against Israel [1]. Likewise, the InCA can also be used to model
cooperation among different actors in performing an attack, including the
relationship between non-state actors and nation-states, such as the potential
connection between Iran and militants stealing UAV feeds in Iraq, or the much-
hypothesized relationship between hacktivist youth groups and the Russian
government [1]. Another aspect that can be modeled is deception where, for
instance, an actor may leave false clues in a piece of malware to lead an
analyst to believe a third party conducted the operation. Such a deception
scenario can be easily created by adding additional rules in the AM that allow
for the creation of such counter-arguments. Another type of deception that
could occur include attacks being launched from a system not in the
responsible party’s area, but under their control (e.g., see [5]). Again,
modeling who controls a given system can be easily accomplished in our
framework, and doing so would simply entail extending an argumentation line.
Further, campaigns of cyber-operations can also be modeled, as well as
relationships among malware and/or attacks (as detailed in [20]).

As with all of these abilities, InCA provides the analyst the means to model a
complex situation in cyber-warfare but saves him from carrying out the
reasoning associated with such a situation. Additionally, InCA results are
constructive, so an analyst can “trace-back” results to better understand how
the system arrived at a given conclusion.

##  5 Conclusion

In this paper we introduced InCA, a new framework that allows the modeling of
various cyber-warfare/cyber-security scenarios in order to help answer the
attribution question by means of a combination of probabilistic modeling and
argumentative reasoning. This is the first framework, to our knowledge, that
addresses the attribution problem while allowing for multiple pieces of
evidence from different sources, including traditional (non-cyber) forms of
intelligence such as human intelligence. Further, our framework is the first
to extend Defeasible Logic Programming with probabilistic information.
Currently, we are implementing InCA and the associated algorithms and
heuristics to answer these queries. We also feel that there are some key areas
to explore relating to this framework, in particular:

  * •

Automatically learning the EM and AM from data.

  * •

Conducting attribution decisions in near real time.

  * •

Identifying additional evidence that must be collected in order to improve a
given attribution query.

  * •

Improving scalability of InCA to handle large datasets.

Future work will be carried out in these directions, focusing on the use of
both real and synthetic datasets for empirical evaluations.

## Acknowledgments

This work was supported by UK EPSRC grant EP/J008346/1 – “PrOQAW”, ERC grant
246858 – “DIADEM”, by NSF grant #1117761, by the Army Research Office under
the Science of Security Lablet grant (SoSL) and project 2GDATXR042, and DARPA
project R.0004972.001.

The opinions in this paper are those of the authors and do not necessarily
reflect the opinions of the funders, the U.S. Military Academy, or the U.S.
Army.

## References

  * [1] P. Shakarian, J. Shakarian, and A. Ruef, _Introduction to Cyber-Warfare: A Multidisciplinary Approach_. Syngress, 2013.
  * [2] C. Altheide, _Digital Forensics with Open Source Tools_. Syngress, 2011.
  * [3] O. Thonnard, W. Mees, and M. Dacier, “On a multicriteria clustering approach for attack attribution,” _SIGKDD Explorations_ , vol. 12, no. 1, pp. 11–20, 2010.
  * [4] L. Spitzner, “Honeypots: Catching the Insider Threat,” in _Proc. of ACSAC 2003_. IEEE Computer Society, 2003, pp. 170–179.
  * [5] “Shadows in the Cloud: Investigating Cyber Espionage 2.0,” Information Warfare Monitor and Shadowserver Foundation, Tech. Rep., 2010.
  * [6] R. J. Heuer, _Psychology of Intelligence Analysis_. Center for the Study of Intelligence.
  * [7] N. J. Nilsson, “Probabilistic logic,” _Artif. Intell._ , vol. 28, no. 1, pp. 71–87, 1986.
  * [8] S. Khuller, M. V. Martinez, D. S. Nau, A. Sliva, G. I. Simari, and V. S. Subrahmanian, “Computing most probable worlds of action probabilistic logic programs: scalable estimation for 10${}^{\mbox{30,000}}$ worlds,” _AMAI_ , vol. 51(2–4), pp. 295–331, 2007.
  * [9] P. Shakarian, A. Parker, G. I. Simari, and V. S. Subrahmanian, “Annotated probabilistic temporal logic,” _TOCL_ , vol. 12, no. 2, p. 14, 2011.
  * [10] G. I. Simari, M. V. Martinez, A. Sliva, and V. S. Subrahmanian, “Focused most probable world computations in probabilistic logic programs,” _AMAI_ , vol. 64, no. 2-3, pp. 113–143, 2012.
  * [11] I. Rahwan and G. R. Simari, _Argumentation in Artificial Intelligence_. Springer, 2009.
  * [12] M. V. Martinez, A. J. García, and G. R. Simari, “On the use of presumptions in structured defeasible reasoning,” in _Proc. of COMMA_ , 2012, pp. 185–196.
  * [13] A. J. García and G. R. Simari, “Defeasible logic programming: An argumentative approach,” _TPLP_ , vol. 4, no. 1-2, pp. 95–138, 2004.
  * [14] J. W. Lloyd, _Foundations of Logic Programming, 2nd Edition_. Springer, 1987.
  * [15] G. R. Simari and R. P. Loui, “A mathematical treatment of defeasible reasoning and its implementation,” _Artif. Intell._ , vol. 53, no. 2-3, pp. 125–157, 1992.
  * [16] F. Stolzenburg, A. García, C. I. Chesñevar, and G. R. Simari, “Computing Generalized Specificity,” _Journal of Non-Classical Logics_ , vol. 13, no. 1, pp. 87–113, 2003.
  * [17] P. M. Dung, “On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and $n$-person games,” _Artif. Intell._ , vol. 77, pp. pp. 321–357, 1995.
  * [18] N. Falliere, L. O. Murchu, and E. Chien, “W32.Stuxnet Dossier Version 1.4,” _Symantec Corporation_ , Feb. 2011.
  * [19] R. Langner, “Matching Langner Stuxnet analysis and Symantic dossier update,” _Langner Communications GmbH_ , Feb. 2011.
  * [20] “APT1: Exposing one of China’s cyber espionage units,” _Mandiant (tech. report)_ , 2013.