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}}$:

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:

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:

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: % latex2html id marker 6285
$\{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:

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:

% latex2html id marker 11309

In this graph, there are 6 cycles:

and 3 mcycles:

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

% latex2html id marker 1553\small
\caption{Algorithm for computing 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)]$,

Marie-Christine Lagasquie 2005-02-04