Computation of tupled values

We propose an algorithm for computing the tupled values for an arbitrary graph (cyclic or acyclic, the cycles may be isolated or not). This algorithm uses a principle of propagation of values: an argument is evaluated when the values of its direct attackers are known.

We must consider the cycles as meta-arguments which are evaluated when all the ``direct attackers of the cycle'' (i.e. the direct attackers of one of the elements of the cycle which do not belong to the cycle) are evaluated.

The beginning of the process is as follows: we consider that all the arguments have the initial value $[0^{\infty},()]$, and only the leaves of the graph are ``marked'' as having their final values. Thus, we have the following partition of the graph ${\mathcal{G}}$:

• ${\mathcal{G}}_v$: the part of the graph already evaluated (at the beginning, this part contains only the leaves of the graph),
• ${\mathcal{G}}_{\lnot v}$: the part of the graph which is not evaluated (at the beginning, this part contains all the arguments of the graph ${\mathcal{G}}$ except the leaves).

The algorithm also relies on a special data structure denoted by ${\mathcal{L}}$ giving the list of the cycles in the graph and their main characteristics:

• list of the arguments which belong to this cycle,
• list of the arguments which belong to this cycle and which have direct attackers outside the cycle (these arguments are called inputs of the cycle; those which will be used in order to propagate the values across the cycle in the case of a non isolated cycle); this list will be empty in the case of an isolated cycle.

Remark: For the sake of efficiency, the interconnected cycles (see Definition 1) will be considered as a ``whole'' by the algorithm and will be used like a ``meta-cycle''. For example, the two cycles $A-B-A$ and $B-C-B$ which do not have any direct attacker outside of the cycles, will be described in the data structure ${\mathcal{L}}$ as only one ``meta-cycle'' with the following lists:

• $A$, $B$, $C$,
• nothing (because it is an isolated ``meta-cycle'').

In order to avoid some ambiguity, these ``meta-cycles'' are defined as mcycles:

Definition 21 (mcycle)   Let ${\mathcal{G}}$ be an attack graph. Let ${\mathcal{C}}{\mathcal{C}}$ be the set of all the cycles of ${\mathcal{G}}$. Let ${\mathcal{C}}{\mathcal{C}}' \subseteq {\mathcal{C}}{\mathcal{C}}$ and ${\mathcal{C}}{\mathcal{C}}' = \{{\mathcal{C}}_1, \ldots, {\mathcal{C}}_n\}$ be a set of cycles.

Let ${\mathcal{A}}_{{\mathcal{C}}{\mathcal{C}}'}$ be the set: $\{A_j \mbox{ such that } \exists {\mathcal{C}}_i \in {\mathcal{C}}{\mathcal{C}}' \mbox{ and } A_j \in {\mathcal{C}}_i\}$.

If ${\mathcal{C}}{\mathcal{C}}'$ satisfies the following properties:

• $\forall A_j, A_k \in {\mathcal{A}}_{{\mathcal{C}}{\mathcal{C}}'}$, $\exists$ a path from $A_j$ to $A_k$ such that each element (arguments or edges between arguments) of the path belongs to cycles of ${\mathcal{C}}{\mathcal{C}}'$,

• and $\forall {\mathcal{C}}_k \in {\mathcal{C}}{\mathcal{C}}\setminus {\mathcal{C}}{\mathcal{C}}'$, $\not\exists {\mathcal{C}}_i \in {\mathcal{C}}{\mathcal{C}}'$ such that ${\mathcal{C}}_k$ is interconnected with ${\mathcal{C}}_i$.

Then the union of the ${\mathcal{C}}_i$ belonging to ${\mathcal{C}}{\mathcal{C}}'$ is a mcycle.

Thus, we make a partition of ${\mathcal{C}}{\mathcal{C}}$ using the notion of interconnection between cycles, each element of the partition being a different mcycle. See on the following example:

In this graph, there are 6 cycles:

• $\{J\}$,
• $\{I,J,K\}$,
• $\{K,L\}$,
• $\{B,C,D\}$,
• $\{C,E\}$,
• $\{F,G\}$.

and 3 mcycles:

• $\{I,J,K,L\}$,
• $\{B,C,D,E\}$,
• $\{F,G\}$.

Algorithm 2 is the main algorithm used for computing the tupled values.

The function ADD-NODE (respectively REMOVE-NODE) whose parameters are a subgraph ${\mathcal{G}}_x$ of the attack graph and a node $s$, adds (resp. removes) $s$ in (resp. of) ${\mathcal{G}}_x$. The other functions are described in [5].

Algorithm 2 has been applied on an example after the step of rewriting (see Figure 1). Note that in order to make the understanding of the results easier, we do not have created new arguments (as in Definitions 11 and 12), but of course, it would be necessary for a rigorous formalization.

Figure 1: Example of rewriting

The previous argumentation graph can be rewritten as follows:

The results of the valuation obtained after one propagation step are:

• $v(A) = [(0,\ldots, 0)()]$,
• $v(B) = [(6,8,8,\ldots)(1,3,5,\ldots)]$,
• $v(C) = [(2,4,6,\ldots)(5,\ldots)]$,
• $v(D) = [(6,\ldots)(3,5,\ldots)]$,
• $v(E) = [(4,6,\ldots)()]$,
• $v(F) = [(8,\ldots)(3,5,5,7,7,\ldots)]$,
• $v(G) = [(2,4,6,\ldots)(7,\ldots)]$,