Jaime Arias
email: arias@lipn.univ-paris13.fr

Laure Petrucci
email: petrucci@lipn.univ-paris13.fr

Łukasz Maśko
email: masko@ipipan.waw.pl

Wojciech Penczek
email: penczek@ipipan.waw.pl

Teofil Sidoruk
email: t.sidoruk@ipipan.waw.pl

Minimal Schedule with Minimal Number of Agents in Attack-Defence Trees

Keywords: attack-defence trees, multi-agent systems, scheduling

Expressing attack-defence trees in a multi-agent setting allows for studying a new aspect of security scenarios, namely how the number of agents and their task assignment impact the performance, e.g. attack time, of strategies executed by opposing coalitions. Optimal scheduling of agents' actions, a non-trivial problem, is thus vital. We discuss associated caveats and propose an algorithm that synthesises such an assignment, targeting minimal attack time and using minimal number of agents for a given attack-defence tree.

I. INTRODUCTION

Security of safety-critical multi-agent systems [START_REF] Wooldridge | An Introduction to Multiagent Systems[END_REF] is a major challenge. Attack-defence trees [START_REF] Kordy | Foundations of Attack-Defense Trees[END_REF], [START_REF] Aslanyan | Pareto Efficient Solutions of Attack-Defence Trees[END_REF] have been developed to evaluate the safety of systems and to study interactions between attacker and defender parties. They provide a simple graphical formalism of possible attacker's actions to be taken in order to attack a system and the defender's defenses employed to protect the system. Recently, it has been proposed to model attack-defence trees (ADTrees) in the formalism of asynchronous multi-agent systems (AMAS) extended with certain ADTree characteristics [START_REF] Petrucci | Squeezing State Spaces of (Attack-Defence) Trees[END_REF], [START_REF] Arias | Hackers vs. Security: Attack-Defence Trees as Asynchronous Multi-agent Systems[END_REF]. In this setting, one can reason about attack/defence scenarios considering agent distributions over tree nodes and their impact on the feasibility and performance (quantified by metrics such as time and cost) of attacking and defending strategies executed by specific coalitions.

A. Minimal schedule with minimal number of agents

The time metric, on which we focus here, is clearly affected by both the number of available agents and their distribution over ADTree nodes. Hence, there arises the problem of optimal scheduling, i.e. obtaining an assignment that achieves the lowest possible time, while using the minimum number of agents required for an attack to be feasible. To that end, we first preprocess the input ADTree, transforming it into a Directed Acyclic Graph (DAG), where specific types of ADTree gates are replaced with sequences of nodes with normalised time (i.e. duration of either zero, or the greatest common factor across all nodes of the original ADTree). Because some ADTree constructs (namely, OR gates and defences) induce multiple alternative outcomes, we execute the scheduling algorithm itself on a number of independently considered DAG variants. For each such variant, we begin by iterating over its nodes, labeling them in accordance with their depth and height in the graph. The lowest possible attack time follows from the longest sequence of nodes in the DAG, because these actions cannot be handled any faster by executing them in parallel. In order to minimise the number of agents as well, we synthesise a schedule multiple times in a divide-and-conquer strategy, adjusting the number of agents until the lowest one that produces a valid assignment is found. Since we preserve labels during the preprocessing step, all DAG nodes are traceable back to specific gates and leaves of the original ADTree. Thus, in the final step we ensure that the same agent is assigned to nodes of the same origin, reshuffling the schedule if necessary.

While there are some clear parallels with multi-processor task scheduling, the ADTree formalism also introduces a number of unique caveats to consider. Consequently, our approach differs from that of classical process scheduling, whose techniques cannot be directly applied in this case. We expand on this comparison in Section I-C.

B. Contributions

In this paper, we: (i) present and prove the correctness of an algorithm for ADTrees which finds an optimal assignment of the minimal number of agents for all possible DAG variants of a given attack/defence scenario, (ii) show the scheduling algorithm's complexity to be quadratic in the number of nodes of its preprocessed input DAG, (iii) implement the algorithm in our tool ADT2AMAS and evaluate experimental results.

C. Related work

ADTrees [START_REF] Kordy | Foundations of Attack-Defense Trees[END_REF], [START_REF] Kordy | Attack-Defense Trees[END_REF] are a popular formalism that has been implemented in a broad range of analysis frameworks [START_REF] Gadyatskaya | Modelling Attack-Defense Trees Using Timed Automata[END_REF]- [START_REF] Aslanyan | Quantitative Verification and Synthesis of Attack-Defence Scenarios[END_REF], comprehensively surveyed in [START_REF] Kordy | DAG-based Attack and Defense Modeling: Don't Miss the Forest for the Attack Trees[END_REF], [START_REF] Widel | Beyond 2014: Formal Methods for Attack Tree-based Security Modeling[END_REF]. They remain extensively studied today [START_REF] Fila | Exploiting Attack-Defense Trees to Find an Optimal Set of Countermeasures[END_REF]. Of particular relevance is the ADTree to AMAS translation [START_REF] Arias | Hackers vs. Security: Attack-Defence Trees as Asynchronous Multi-agent Systems[END_REF], based on the semantics from [START_REF] Jamroga | Towards Partial Order Reductions for Strategic Ability[END_REF]. Furthermore, the problem discussed in this paper is clearly related to parallel program scheduling [START_REF] Adam | A Comparison of List Schedules for Parallel Processing Systems[END_REF], [START_REF] Kwok | Static Scheduling Algorithms for Allocating Directed Task Graphs to Multiprocessors[END_REF]. Due to time normalisation, it falls into the category of Unit Computational Cost (UCC) graph scheduling problems, which can be effectively solved for tree-like structures [START_REF] Hu | Parallel Sequencing and Assembly Line Problems[END_REF], but cannot be directly applied to a set of DAGs. Although a polynomial solution for interval-ordered DAGs was proposed by [START_REF] Papadimitriou | Scheduling Interval-Ordered Tasks[END_REF], their algorithm does not guarantee the minimal number of agents. Due to zero-cost communication in all considered graphs, the problem can also be classified as No Communication (NC) graph scheduling. A number of heuristic algorithms using list scheduling were proposed [START_REF] Adam | A Comparison of List Schedules for Parallel Processing Systems[END_REF], including Highest Levels First with No Estimated Times (HLFNET), Smallest Colevels First with no Estimated Times (SCFNET), and Random, where nodes in the DAG are assigned priorities randomly. Variants assuming non-uniform node computation times are also considered, but are not applicable to the problem solved in this paper. Furthermore, this class of algorithms does not aim at finding a schedule with the minimal number of processors or agents. On the other hand, known algorithms that include such a limit, i.e. for the Bounded Number of Processors (BNP) class of problems, assume non-zero communication cost and rely on the clustering technique, reducing communication, and thus schedule length, by mapping nodes to processing units. Hence, these techniques are not directly applicable.

The algorithm described in this paper can be classified as list scheduling with a fusion of HLFNET and SCFNET heuristics, but with additional restriction on the number of agents used. The length of a schedule is determined as the length of the critical path of a graph. The number of minimal agents needed for the schedule is found with bisection.

Branching schedules analogous to the variants discussed in Section III have been previously explored, albeit using different models that either include probability [START_REF] Towsley | Allocating Programs Containing Branches and Loops Within a Multiple Processor System[END_REF] or require an additional DAG to store possible executions [START_REF] El-Rewini | Static Scheduling of Conditional Branches in Parallel Programs[END_REF]. Zero duration nodes are also unique to the ADTree setting.

To the best of our knowledge, this is the first work dealing with agents in this context. Rather, scheduling in multi-agent systems typically focuses on agents' choices in cooperative or competitive scenarios, e.g. in models such as BDI [START_REF] Nunes | Softgoal-based Plan Selection in Model-driven BDI Agents[END_REF], [START_REF] Dann | Intention-Aware Multiagent Scheduling[END_REF].

D. Outline

The rest of the paper is structured as follows. The next section briefly recalls the ADTree formalism and its translation to multi-agent systems. In Section III, several preprocessing steps are discussed, including transforming the input tree to a DAG, normalising node attributes, and handling different types of nodes. Section IV presents steps performed by the main algorithm, as well as a proof of its correctness and optimality. The algorithm, implemented in our tool ADT2AMAS [START_REF] Arias | ADT2AMAS: Managing Agents in Attack-Defence Scenarios[END_REF], is demonstrated in practice on three use cases in Section V. The final section contains conclusions and perspectives.

II. ATTACK-DEFENCE TREES

To keep the paper self-contained, we briefly recall the basics of ADTrees and their translation to a multi-agent setting.

A. Attack-defence trees

ADTrees are a well-known formalism that models security scenarios as an interplay between attacking and defending parties. Figure 1 depicts basic constructs used in examples throughout the paper. For a more comprehensive overview, we refer the reader to [START_REF] Arias | Hackers vs. Security: Attack-Defence Trees as Asynchronous Multi-agent Systems[END_REF].

a (a) leaf (attack) A a1 an • • • (b) AND A a1 an • • • (c) OR A a1 an • • • (d) SAND d (e) leaf (defence) A a d (f) CAND A a d (g) NODEF A a d (h) SCAND Fig. 1: Basic ADTree constructs
Attacking and defending actions are depicted in red and green, respectively. Leaves represent individual actions at the highest level of granularity. Different types of gates allow for modeling increasingly broad intermediary goals, all the way up to the root, which corresponds to the overall objective. OR and AND gates are defined analogously to their logical counterparts. SAND is a sequential variant of the latter, i.e. the entire subtree a i needs to be completed before handling a i+1 . Although only shown in attacking subtrees here, these gates may refine defending goals in the same manner. Reactive or passive countering actions can be expressed using gates CAND (counter defence; successful iff a succeeds and d fails), NODEF (no defence; successful iff either a succeeds or d fails), and SCAND (failed reactive defence; sequential variant of CAND, where a occurs first). We collectively refer to gates and leaves as nodes.

ADTree nodes may additionally have numerical attributes, e.g. the time needed for an attack, or its financial cost. Boolean functions over these attributes, called conditions, may then be associated with counter-defence nodes to serve as additional constraints for the success or failure of a defending action.

In the following, the treasure hunters ADTree in Figure 2 will be used as a running example. While both the gatekeeper b and the door f need to be taken care of to steal the treasure (ST), just one escape route (either h or e) is needed to flee (GA), with TF enforcing sequentiality. Note the TS counter defence with an additional constraint on the police's success p.

B. Translation to extended AMAS

Asynchronous multi-agent systems (AMAS) [START_REF] Jamroga | Towards Partial Order Reductions for Strategic Ability[END_REF] are essentially networks of automata, which synchronise on shared transitions and interleave private ones for asynchronous execution. An extension of this formalism with attributes and conditional constraints to model ADTrees, and the translation of the latter to extended AMAS, were proposed in [START_REF] Arias | Hackers vs. Security: Attack-Defence Trees as Asynchronous Multi-agent Systems[END_REF]. Intuitively, each node of the ADTree corresponds to a single automaton in the resulting network. Specific patterns, embedding reductions to minimise state space explosion [START_REF] Petrucci | Squeezing State Spaces of (Attack-Defence) Trees[END_REF], are used for different types (b) Attributes of nodes Fig. 2: Running example: treasure hunters of ADTree constructs. As the specifics exceed the scope and space of this paper, we refer the reader to [START_REF] Jamroga | Towards Partial Order Reductions for Strategic Ability[END_REF] for the AMAS semantics, and to [START_REF] Arias | Hackers vs. Security: Attack-Defence Trees as Asynchronous Multi-agent Systems[END_REF] for the details on the translation.

In the multi-agent setting, groups of agents working for the attacking and defending parties can be considered. Note that the feasibility of an attack is not affected by the number or distribution of agents over ADTree nodes, as opposed to some performance metrics, such as time (e.g. a lone agent can handle all the actions sequentially, albeit usually much slower).

C. Assignment of agents for ADTrees

Consequently, the optimal distribution of agent coalitions is of vital importance for both parties, allowing them to prepare for multiple scenarios, depending on how many agents they can afford to recruit (thereby delaying or speeding up the completion of the main goal). For instance, the thieves in Figure 2, knowing the police response time, would have to plan accordingly by bringing a sufficiently large team and, more importantly, schedule their tasks to make the most of these numbers. Thus, we can formulate two relevant and non-trivial scheduling problems. The first one, not directly addressed here, is obtaining the assignment using a given number of agents that results in optimal execution time. The second one, on which we focus in this paper, is synthesising an assignment that achieves a particular execution time using the least possible number of agents. Typically, the minimum possible time is of interest here. As we show in Section III, this time is easily obtainable from the structure of the input ADTree itself (and, of course, the time attribute of nodes). However, our approach can also target a longer attack time if desired. In the next section, we discuss it in more detail as normalisation of the input tree is considered, along with several other preprocessing steps.

III. PREPROCESSING THE TREE

In this preprocessing step, an ADTree is transformed into DAGs (Directed Acyclic Graphs) of actions of the same duration. This is achieved by splitting nodes into sequences of such actions, mimicking the scheduling enforced by ADTrees sequential gates, and considering the different possibilities of defences. Therefore, we introduce a sequential node SEQ, which only waits for some input, processes it and produces some output. It is depicted as a lozenge (see nodes N 1 and N 2 in Figure 3).

In what follows, we assume one time unit is the greatest common factor of time durations across all nodes in the input ADTree, i.e. t unit = gcf (t N1 . . . t N |ADT ree| ). By time slots, we refer to fragments of the schedule whose length is t unit . That is, after normalisation, one agent can handle exactly one node of non-zero duration within a single time slot. Note that, during the preprocessing steps described in this section, node labels are preserved to ensure backwards traceability. Their new versions are either primed or indexed.

A. Nodes with no duration

It happens that several nodes have no time parameter set, and are thus considered to have a duration of 0. Such nodes play essentially a structuring role. Since they do not take any time, the following proposition is straightforward.

Proposition 1. Nodes with duration 0 can always be scheduled immediately before their parent node or after their last occurring child, using the same agent in the same time slot.

Preprocessing introduces nodes similar to SEQ but with 0 duration, called NULL and depicted as trapeziums (Fig. 4).

B. Normalising time

The first pre-processing step prior to applying the scheduling algorithm normalises the time parameter of nodes.

Proposition 2. Any node N of duration t N = n×t unit , n ̸ = 0 can be replaced with an equivalent sequence consisting of a node N ′ (differing from N only in its 0 duration) and n SEQ nodes N 1 , . . . , N n of duration t unit .

N ′ N 1 N 2 lt rt N lt rt
Example 1. Figure 3 shows the transformation of an AND node N with duration t N = 2t unit . Both N 2 and N 1 are of duration t unit , while N ′ has a null duration.

C. Scheduling enforcement

Sequential nodes SAND enforce some scheduling. These are transformed into a sequence containing their subtrees and NULL nodes. Proposition 3. Any SAND node N with children subtrees T 1 , . . . , T n can be replaced with an equivalent sequence T 1 , N 1 , T 2 , . . . , N n-1 , T n , N n , where each N i is a NULL node, its input is the output of T i and its outputs are the leaves of T i+1 (except for N n which has the same output as N if any). The scheduling we are seeking to obtain will guarantee the necessary attacks are performed. Hence, when dealing with defence nodes, we can assume that all attacks are successful. However, they may not be mandatory, in which case they should be avoided so as to obtain a better scheduling of agents.

Taking into account each possible choice of defences will lead to as many DAGs representing the attacks to be performed. This allows for answering the question: "What is the minimal schedule of attacker agents if these defences are operating?"

Composite defences. Defences resulting from an AND, SAND or OR between several defences are operating according to the success of their subtrees: for AND and SAND, all subtrees should be operating, while only one is necessary for OR. This can easily be computed by a boolean bottom-up labelling of nodes. Note that different choices of elementary defences can lead to disabling the same higher-level composite defence, thus limiting the number of DAGs that will need to be considered for the scheduling.

No Defence nodes (NODEF). A NODEF succeeds if its attack succeeds or its defence fails. Hence, if the defence is not operating, the attack is not necessary. Thus, the NODEF node can be replaced by a NULL node without children, and the children subtrees deleted. On the contrary, if the defence is operating, the attack must take place. The defence subtree is deleted, while the attack one is kept, and the NODEF node can be replaced by a NULL node, as pictured in Figure 5.

Counter Defence (CAND) and Failed Reactive Defence (SCAND) nodes. A CAND succeeds if its attack is successful and its defence is not. A SCAND behaves similarly but in a sequential fashion, i.e. the defence takes place after the attack. In both cases, if the defence is not operating, its subtree is deleted, while the attack one is kept, and the CAND (or SCAND) node can be replaced by a NULL node, as was the case in Figure 5c. Otherwise, the CAND (or SCAND) node is deleted, as well as its subtrees. Moreover, it transmits its failure recursively to its parents, until a choice of another branch is possible. Thus, all ancestors are deleted bottom up until an OR is reached.

Thus, we have a set of DAGs with attack nodes only. OR nodes give the choice between several series of actions, only one of which will be chosen in an optimal assignment of events. However, one cannot simply keep the shortest branch of an OR node and prune all others. Doing so minimises attack time, but not necessarily the number of agents. In particular, a slightly longer, but narrower branch may require fewer agents without increasing attack time, provided there is a longer sequence elsewhere in the DAG. Consequently, only branches that are guaranteed not to lead to an optimal assignment can be pruned, which is the case when a branch is the longest one in the entire graph. All other cases need to be investigated, leading to multiple variants depending on the OR branch executed, similar to the approach for defence nodes.

F. Preprocessing the treasure hunters ADTree

Figures 6 and7 detail the preprocessing of the treasure hunters example step by step. The time unit is one minute. Long sequences of SEQ are shortened with dotted lines. Note that when handling the defence, at step 3, we should obtain two DAGs corresponding to the case where the defence fails (see Figure 7b), or where the defence is successful. This latter case leads to an empty DAG where no attack can succeed. Therefore, we can immediately conclude that if the police is successful, there is no scheduling of agents.

IV. BEST MINIMAL AGENT ASSIGNMENT

At this stage, we have DAGs where nodes are either (i) a leaf, or of type AND, OR, or NULL, all with duration 0 or (ii) of type SEQ with duration t unit . Their branches mimic the possible runs in the system. The algorithm's input is a set of DAGs preprocessed as described in Section III, corresponding to possible configurations of defence nodes' outcomes and choices of OR branches in the original ADTree. For each of these DAGs, n denotes the number of SEQ nodes (all other ones have 0-duration). Furthermore, nodes (denoted by N ) have some attributes: their type; four integers depth, level , agent and slot, initially with value 0. The values of depth and level denote, respectively, the height of a node's tallest subtree and the distance from the root (both without counting the zero duration nodes), while agent and slot store a node's assignment in the schedule. We first compute the nodes' depth in Section IV-A, then compute the level of nodes in Section IV-B, and finally compute an optimal scheduling in Section IV-D.

TS ′ p10 p1 p ′ TF ′ ST2 ST1 ST ′ b60 b1 b ′ f120 f1 f ′ GA ′ h3 h2 h1 h ′ e10 e1 e ′

A. Depth of nodes

Starting from the root, the procedure DEPTHNODE (Algorithm 1) explores the DAG in a DFS (depth first search) manner. During backtracking, i.e. starting from the leaves, depth is computed for the different types of nodes as follows:

LEAF node: After the time normalisation, a leaf node takes 0 time. It may still be an actual leaf, and its total duration is also 0 since it has no children (not satisfying condition at l. 3). Or, it may have a child due to scheduling enforcement, and then its time is the same as the one of its only child (l. 10).

SEQ node: Its duration is one t unit , which must be added to the duration of its only child to obtain the minimum time of execution from the start (l. [START_REF] Petrucci | Squeezing State Spaces of (Attack-Defence) Trees[END_REF][START_REF] Arias | Hackers vs. Security: Attack-Defence Trees as Asynchronous Multi-agent Systems[END_REF].

AND node: All children must be completed before it occurs. Therefore, its minimal time is the maximum one of all its children (l. 6-7).

OR node: One child must complete for the OR node to happen. Its time is thus the minimal one of all its children (l. [START_REF] Arnold | Sequential and Parallel Attack Tree Modelling[END_REF][START_REF] Gribaudo | Exploiting Bayesian Networks for the Analysis of Combined Attack Trees[END_REF].

NULL node: Note that, by construction, a NULL node may have several parents but a single child. Its duration being null, its time is the same as the one of its only child (l. 10).

Note that the condition at l. 2 avoids a second exploration of a node which has already been handled in another branch.

Algorithm 1: DEPTHNODE(node)

1 for N ∈ child (node) do 2 if N.depth = 0 then DEPTHNODE(N ) 3 if child (node) ̸ = ∅ then

B. Level of nodes

Levels are assigned recursively, starting with the root, using a DFS. The procedure LEVELNODE (Algorithm 2) computes nodes' levels. It first assigns the node's level (l. 1) according to the call argument. Note that in case of multiple parents (or ancestors with multiple parents), the longest path to the root is kept. The upper bound on the number of agents is obtained from the maximal width of the preprocessed DAG, i.e. the maximal number of SEQ nodes assigned the same value of level (that must be executed in parallel to ensure minimum time).

The minimal attack time is obtained from the number of levels l in the preprocessed DAG. Note that the longest path from the root to a leaf has exactly l nodes of non-zero duration. Clearly, none of these nodes can be executed in parallel, therefore the number of time slots cannot be smaller than l. Thus, if an optimal schedule of l × t unit is realisable, the n nodes must fit in a schedule containing l time slots. Hence, the lower bound on the number of agents is ⌈ n l ⌉. There is, however, no guarantee that it can be achieved, and introducing additional agents may be necessary depending on the DAG structure, e.g. if there are many parallel leaves.

D. Minimal schedule

The algorithm for obtaining a schedule with the minimal attack time and also minimising the number of agents is given in Algorithm 3. Input DAGs are processed sequentially, a schedule returned for each one. Not restricting the output to the overall minimum allows to avoid "no attack" scenarios where the time is 0 (e.g. following a defence failure on a root NODEF node). Furthermore, with information on the repartition of agents for a successful minimal time attack in all cases of defences, the defender is able to decide which defences to enable according to these results (and maybe the costs of defences).

The actual computation of the schedule is handled by the function SCHEDULE (Algorithm 4). Starting from the root and going top-down, all SEQ nodes at the current level are added to set S. The other nodes at that level have a null duration and can be scheduled afterwards with either a parent or child. An additional check in l. 5 ensures that non-optimal variants (whose longest branch exceeds a previously encountered minimum) are discarded without needlesly computing the schedule. Nodes in S are assigned an agent and time slot, prioritising those with higher depth (i.e. taller subtrees), as long as an agent is available. Assigned nodes are removed from S, and any that remains (e.g. when the bound was exceeded) is carried over to the next level iteration. Note that at this point it is possible for a parent and child node to be in S concurrently, but since higher depth takes precedence, they will never be scheduled in the wrong order. In such cases, an extra check in the while loop avoids scheduling both nodes to be executed in parallel.

Algorithm 4 calls function RESHUFFLESLOT after the complete assignment of a time slot at l. 12 to ensure consistent assignment of sub-actions of the same ADTree node. Note that depending on depth, a sub-action may be moved to the next slot, creating an interrupted schedule where an agent stops an action for one or more time units to handle another. Alternatively, agents may collaborate, each handling a node's action for a part of its total duration. Such assignments could be deemed unsuitable for specific scenarios, e.g. defusing At this point, either the upper or the lower bound on the number of agents is adjusted, depending on whether the resulting schedule is valid (that is, there are no nodes left to assign at the end). Scheduling is then repeated for these updated values until the minimal number of agents is found (i.e. the two bounds are equal).

After the complete computation for a given DAG, l. 22 calls function ZEROASSIGN in order to obtain assignments for all remaining nodes, i.e. those of zero duration. Functions RESHUFFLESLOT and ZEROASSIGN are detailed in Sections IV-E and IV-F, respectively.

Although this algorithm assumes the minimal time is of interest, it can be easily modified to increase the number of time slots, thus synthesising the minimal number of agents required for a successful attack of any given duration.

E. Uniform assignment for SEQ nodes

A separate subprocedure, given in Algorithm 5, swaps assigned agents between nodes at the same level so that the same agent handles all SEQ nodes in sequences obtained during Proof. First, note that the procedure does not affect nodes whose parents have not yet been assigned an agent (l. 4). Hence, reshuffling only applies to SEQ nodes (since the assignment of 0 duration nodes occurs later in the main algorithm MINSCHEDULE). Furthermore, changes are restricted to pairs of nodes in the same time slot, so swapping assigned agents between them cannot break the execution order and does not affect the schedule correctness.

F. Assigning nodes without duration

After all non-zero duration nodes have been assigned and possibly reshuffled at each level, Algorithm 6 handles the remaining nodes.

Our choice here stems from the ADTree gate the node originates from. We first assign zero-duration nodes to the Of the remaining ones, nodes of type NULL, OR and LEAF get the same assignment as their only child if any, or as their parent if they have no child (l. [START_REF] Arnold | Sequential and Parallel Attack Tree Modelling[END_REF][START_REF] Gribaudo | Exploiting Bayesian Networks for the Analysis of Combined Attack Trees[END_REF][START_REF] Aslanyan | Quantitative Verification and Synthesis of Attack-Defence Scenarios[END_REF][START_REF] Kordy | DAG-based Attack and Defense Modeling: Don't Miss the Forest for the Attack Trees[END_REF][START_REF] Widel | Beyond 2014: Formal Methods for Attack Tree-based Security Modeling[END_REF][START_REF] Fila | Exploiting Attack-Defense Trees to Find an Optimal Set of Countermeasures[END_REF][START_REF] Jamroga | Towards Partial Order Reductions for Strategic Ability[END_REF][START_REF] Adam | A Comparison of List Schedules for Parallel Processing Systems[END_REF][START_REF] Kwok | Static Scheduling Algorithms for Allocating Directed Task Graphs to Multiprocessors[END_REF][START_REF] Hu | Parallel Sequencing and Assembly Line Problems[END_REF][START_REF] Papadimitriou | Scheduling Interval-Ordered Tasks[END_REF][START_REF] Towsley | Allocating Programs Containing Branches and Loops Within a Multiple Processor System[END_REF]. The latter case may happen for NULL when handling defences as in e.g. Figure 5b, and for LEAF nodes with originally a null duration. AND nodes are assigned the same agent and time slot as the child that occurs last (l. 20-30).

Note that in all cases the agents (and time slots) assigned to zero duration nodes are the same as those of their immediate parents or children. Hence, no further reshuffling is necessary. Proposition 5. Adding nodes of zero duration to the assignment in Algorithm 6 does not affect the correctness of the scheduling.

Proof. Since all remaining nodes have zero duration, no extra agents or time slots are necessary. In all cases, the zero duration node is assigned with either its immediate parent or child, preserving the correct execution order. Consider possible cases at each step of the algorithm:

• l. 2-6: Nodes with a SEQ parent are the final nodes of sequences obtained during time normalisation. Clearly, they can be assigned the same agent and time slot as their immediate parent without affecting the schedule. • l. 8-19: OR nodes: in each DAG variant (see Section III-E), they are guaranteed to have a single child node and can be scheduled together with this child provided the corresponding sub-DAG has some duration. NULL and LEAF nodes have a single child if any and are handled analogously to OR, being assigned the same agent as their child. Note that LEAF nodes can have gotten this child during e.g. the scheduling enforcement step (see Section III-C).

OR, NULL and LEAF nodes with no child or a child sub-DAG with no duration are assigned as their parent.

If a NULL node has several parents due to sequence enforcement, it gets the same assignment as its parent that occurs first. • l. 20-30: In case all children are never able to get an assignment, i.e. they are subtrees of null duration and can be identified with a depth 0, the AND node gets the same assignment as its parent.

Otherwise, AND nodes are also scheduled together with one of their children. Note that the AND condition is satisfied only if all its longest children have completed, therefore the one that occurs last, i.e. has the biggest time slot, is chosen (l. 20-30). Furthermore, note that since children subtrees with a null duration are discarded, such children of the AND node have already been assigned an agent at that point. The pathological case of a full ADTree with no duration is not handled since the algorithm is not called for such DAGs.

G. Complexity and correctness

We now consider the algorithm's complexity and prove that it achieves its intended goal. Proposition 6. Algorithm 3 is in O(kn 2 log n), where k is the number of input DAG variants, and n their average number of nodes.

Proof. Initially, DEPTHNODE, and LEVELNODE each visit all DAG nodes, hence 2n operations. In SCHEDULE, the outer while loop (l. 2) iterates over nodes of non-zero duration; its inner loop and RESHUFFLESLOT both operate within a single time slot. Overapproximating these numbers by n puts the function at no more than n 2 operations. The schedule computation is repeated at most log n times in a divide-andconquer strategy (l. 13).

Finally, ZEROASSIGN visits all zero duration nodes (again overapproximated by n), performing at most 2n iterations for each, for a total of 2n 2 . Thus, the complexity of processing a single DAG is O(2n + n 2 log n + 2n 2 ) = O(n 2 log n), and O(kn 2 log n) for the whole input set.

Note that as per Section III, the preprocessing step introduces a number of additional nodes in resulting DAGs. However, since that factor depends on the structure and attributes of the original ADTree rather than its size, it is treated as a constant in the consideration of complexity. Thus, while the complexity of the scheduling algorithm itself is quadratic, it is executed for k input DAG variants, where k is exponential in the number of OR and defence nodes in the ADTree.

Proposition 7. The assignments returned by Algorithm 3 are correct and use the minimal number of agents for each variant DAG ∈ DAG set to achieve the attack in minimal time.

Proof. Let L denote the number of levels in an input variant DAG ∈ DAG set, and L i the set of nodes at the i-th level. We need to show that the resulting assignment is 1) correct, and 2) optimal in both schedule length and number of agents.

1) SCHEDULE assigns time slot 1 to leaves at the bottom level, subsequent slots to their ancestors, and finally the last one L to the root node. Thus, the execution order of nodes in DAG is correct. Furthermore, it is guaranteed that there are enough agents to handle all nodes by increasing agents accordingly after an invalid assignment with unassigned nodes is discarded (l. [START_REF] Jamroga | Towards Partial Order Reductions for Strategic Ability[END_REF], and that any nodes executed in parallel (i.e. at the same level) are assigned to different agents (l. 10). Note also that the while loop at l. 13 of MINSCHEDULE is guaranteed to terminate as the value of agents is refined from its theoretical bounds in a divide-and-conquer strategy.

2) Since the number of time slots is fixed at L (Algorithm 3, l. 8), i.e. the minimal value that follows directly from the structure of DAG as its longest branch (note that L = root(DAG).depth), it follows that the total attack time L × t unit is always minimal.

To show that the number of agents is also minimal, consider the assignment of nodes at each level L i of DAG. The case for the top level L 0 is trivial: it only contains the root node, which cannot be executed in parallel with any other and thus can be assigned to any agent. By induction on subsequent levels L i , we can show agents are also optimally assigned at each one. Suppose that the assignment of agents and time slots for all nodes down to and including level L i is optimal. At L i+1 , there are two possibilities to consider. If |L i+1 | ≤ agents, some agents are idle in this time slot. However, this assignment cannot be improved upon: note that any lower values of agents would have already been checked during earlier cycles of the while loop (l. 13), and found to produce an invalid schedule where some nodes are left without any agent asssigned (l. 16).

Conversely, if |L i+1 | > agents, some nodes will be carried over to L i+2 . Similarly, it follows from the divide-and-conquer scheme in which the final value of agents is obtained (l. 13) that decreasing the number of agents further is impossible without adding an extra slot instead.

Therefore, the assignment up to level L i+1 cannot be improved and is optimal for a schedule containing L time slots.

Note that subsequently executed subprocedures RESHUF-FLESLOT and ZEROASSIGN do not affect this in any way, since neither adds extra agents or time slots.

Thus, for any DAG ∈ DAG set, schedule length is fixed at its theoretical minimum, and the optimality of agent assignment for this minimal length follows from the fact time slots are filled exhaustively wherever possible, but using the lowest number of agents that does not leave unassigned nodes (i.e. an invalid schedule). Since all input DAG variants are equivalent to the original ADTree w.r.t. scheduling (by Propositions 1 to 3), it also holds that the assignment is optimal for the original ADTree.

H. Scheduling for the treasure hunters ADTree

We now apply these algorithms to the treasure hunters example. Figure 7c shows the output of the three initial subprocedures. The depth of nodes assigned by Algorithm 1 is displayed in green. The branch corresponding to attack e has been pruned as per Section III-E. Levels assigned by Algorithm 2 are displayed in blue. Finally, the agents assignment computed by Algorithm 3 is shown in Figure 8. We have implemented the algorithms presented in this paper in our open source tool ADT2AMAS [START_REF]ADT2AMAS: Tool for Managing Agents in Attack-Defense Scenarios[END_REF], written in C++17. It allows for specifying input ADTrees either via simplesyntax text files or using an intuitive graphical user interface, and handles both their translation to extended AMAS and subsequent computation of an optimal schedule with minimal number of agents. Furthermore, intermediary steps of the algorithm can be exported as Tikz figures, allowing to easily visualise and understand them. For more detailed information on the architecture of ADT2AMAS, we refer the reader to [START_REF] Arias | ADT2AMAS: Managing Agents in Attack-Defence Scenarios[END_REF].

slot agent 1 2 125 h 3 , GA ′ , TF ′ 2 , TS ′ 124 h 2 123 h 1 , h ′ 122 ST 2 , TF ′ 1 121 ST 1 , ST ′ 120 f 120 b 60 • • • • • • • • • 61 f 61 b 1 , b ′ 60 f 60 • • • • • • 1 f 1 , f ′
In the following, we present its application to the use cases from [START_REF] Arias | Hackers vs. Security: Attack-Defence Trees as Asynchronous Multi-agent Systems[END_REF], plus examples that feature some specific behaviour. The user can find all the figures and tables of the examples in the supplementary material of this paper, which is available at https://up13.fr/?nkPtK4eY.

forestall: This case study models forestalling a software instance. Depending on the active defences, 4 cases are possible. However, the DAG for no active defence or only id active is the same. All three remaining DAGs have an optimal schedule with only 1 agent, in 43 days for the no defence (or id only) case, 54 if only scr is active, and 55 if both defences occur. Although only a single agent is needed to achieve the attack in minimal time, the schedule exhibits which specific attacks must be performed to do so.

iot-dev: This example models an attack on an IoT device via a network. There are 4 cases, according to the active defences, but only the one with no defence leads to a DAG. Indeed, tla causes the failure of GVC which in turn makes APN and then APNS fail, independent of inc. Thus the attack necessarily fails. This is also the case if defence inc is active. The only way for an attack to succeed is that all defences fail, leading to an optimal schedule in 694 minutes with 2 agents. Hence an attacker will use 2 agents to perform the fastest attack. On the other hand, the defender knows that a single one of the two defences is sufficient to block any attack.

gain-admin: This third case study features an attacker trying to gain administration privileges on a computer system. There are 16 possible defences combinations, which are covered by only 3 cases: scr is not active; scr is active but not DTH; both of them are active. In all three cases, the shortest attack requires only a single agent, and can be scheduled in 2942, 4320 and 5762 minutes, respectively.

Exhibiting particular scheduling features: Experiments were conducted on the example used in [START_REF] Arias | Hackers vs. Security: Attack-Defence Trees as Asynchronous Multi-agent Systems[END_REF] to evaluate the impact of the number of agents on the attack time and two small examples designed to exhibit particular characteristics of the schedule. Our algorithm confirms an optimal schedule in 5 minutes with 6 agents for the example of [START_REF] Arias | Hackers vs. Security: Attack-Defence Trees as Asynchronous Multi-agent Systems[END_REF]. Then, interrupted shows that the scheduling algorithm can produce an the interleaved execution of two attacks (b and e), assigned to the same agent. Finally, the last example provides a succession of nodes with 0 duration ( a ′ , e ′ , f ′ , h ′ and i ′ ), and shows they are handled as expected.

Scaling example: In the scaling example, the first agent processes the longest path while the second agent handles all other actions. It is extended to analyse the scaling capabilities of the scheduling algorithm. For this purpose, we wrote an automatic generator of ADTrees and a notebook that processes the output of our tool in order to create Figure 9. The parameters of the generated ADTrees are the depth, the width corresponding to the number of deepmost leaves, the number of children for each AND, and the total number of nodes. All nodes have time 1 except the first leaf that has time width -1. The results show that the number of agents is not proportional to the width of the tree (red bars -top of Figure 9), and the optimal scheduling varies according to the time of nodes (blue bars -bottom of Figure 9).

VI. CONCLUSION

This paper has presented an agents scheduling algorithm that allows for evaluating attack/defence models. It synthesises a minimal number of agents and their schedule, providing insight to both parties as to the number of agents and actions necessary for a successful attack, and the defences required to counter it. While the scheduling algorithm itself is optimal, further improvements can be made in the number of DAG variants it is executed on. One possible approach involves encoding configurations induced by OR and defence nodes to SAT or SMT and using a solver to find the optimal one, to be passed to the algorithm. A natural extension is to consider characteristics other than time (e.g. cost) and, more importantly, the additional constraints on nodes, thereby obtaining a complete framework for not only analysis but also synthesis of agent configurations and schedules to achieve a given goal in a multi-agent system. Targeting more elaborate goals, expressed in the TATL logic [START_REF] Knapik | Timed ATL: Forget Memory, Just Count[END_REF], will allow for analysing more general multi-agent systems and their properties.

Fig. 3 :

 3 Fig. 3: Normalising AND node N (t N = 2t unit , t N ′ = 0)

Example 2 .

 2 Let us consider the SAND node N depicted on the left-hand side of Figure4, where all other nodes have already been processed by the time normalisation. The transformation of Proposition 3 leads to the DAG on the righthand side of Figure4where subtrees A, B and C occur in sequence, as imposed by the NULL nodes N 1 and N 2 between them, and then action N 3 occurs.

Fig. 4 :

 4 Fig. 4: Normalising SAND node N

Fig. 5 :

 5 Fig. 5: Handling NODEF A

Fig. 6 :Fig. 7 :

 67 Fig. 6: Treasure hunters ADTree: time normalisation

4 if

 4 node.type = SEQ then 5 node.depth ← N.depth + 1, s.t. {N } = child (node) 6 else if node.type = AND then 7 node.depth ← max({N.depth | N ∈ child (node)}) 8 else if node.type = OR then 9 node.depth ← min({N.depth | N ∈ child (node)}) 10 else node.depth ← N.depth, s.t. {N } = child (node)

Algorithm 2 :

 2 LEVELNODE(node, l) 1 node.level ← max(l, node.level ) 2 for N ∈ child (node) do 3 if node.type = SEQ then LEVELNODE(N, l + 1) 4 else LEVELNODE(N, l) C. Number of agents: upper and lower bounds

Algorithm 3 : 3 Pick DAG ∈ DAG set 4 if

 334 MINSCHEDULE(DAG set) 1 output = ∅ 2 while DAG set ̸ = ∅ do DAG.n = 0 then continue ▷ Skip empty DAGs 5 DEPTHNODE(root(DAG)) ▷ Compute depth of nodes 6 DAG ← DAG \ {N | ¬N.keep} 7 LEVELNODE(root(DAG), 0)

Algorithm 4 : 3 agent ← 1 4S 6 return ∅, n remain 7 while 8 N.agent ← agent 9 N.slot ← slot 10 agent ← agent + 1 , 11 S ← S \ {N } 12 RESHUFFLESLOT(slot, agent - 1 ) 13 l

 43167891011112113 SCHEDULE(DAG, slots, agents)1 l ← 0, slot ← slots, S ← ∅, n remain ← DAG.n 2 while n remain > 0 and slot > 0 do ← S ∪ {N | N.type = SEQ ∧ N.level = l} 5 if ∃ N ∈S , s.t. N.depth < slots -slot then agent ≤ agents and S ̸ = ∅ and (Pick N ∈ S, s.t. ∀ N ′ ∈S N.depth ≥ N ′ .depth ∧ ∀ N ′ :N ′ .slot=slot N ′ / ∈ ancestors(N )) ̸ = ∅ do n remain ← n remain -1 ← l + 1, slot ← slot -1 14 output ← N ∈DAG {(N.agent, N.slot)} 15 return output, n remain the time normalisation step (i.e. corresponding to a single node in the original ADTree).

Algorithm 5 : 6 N 7 N ′ .slot ← slot 8 current node.agent ← par agent 9 current node.slot ← slot Proposition 4 .

 567894 RESHUFFLESLOT(slot, num agents) 1 for agent ∈ {1..num agents} do 2 current node ← N , s.t. N.agent = agent ∧ N.slot = slot 3 par agent ← parent(current node).agent 4 if par agent ̸ = agent ∧ par agent ̸ = 0 then 5 if ∃N ′ ̸ = current node, s.t. N ′ .agent = par agent ∧ N ′ .slot = slot then ′ .agent ← agent ▷ Swap with N ′ if it exists Reshuffling the assignment by swapping the agents assigned to a pair of nodes in the same slot does not affect the correctness of the scheduling.

Algorithm 6 : 6 S 12 S 24 S ← S \ {node} 25 if

 66122425 ZEROASSIGN(DAG) 1 S ← {N | N.agent = 0} ▷ Nodes not assigned yet 2 for node ∈ S do 3 if N ∈ parent(node) ∧ N.type = SEQ then 4 node.agent ← N.agent 5 node.slot ← N.slot ← S \ {node} 7 while S ̸ = ∅ do 8 for node ∈ S s.t. node.type ∈ {NULL, OR, LEAF} do 9 if N.agent ̸ = 0 s.t. N ∈ child (node) then 10 node.agent ← N.agent 11 node.slot ← N.slot ← S \ {node} 13 if (child (node) = ∅ 14 ∨(N.depth = 0 s.t. N ∈ child (node))) then 15 parent node ← N ∈ parent(node) s.t. ∀ N ′ ∈parent(node) N.slot ≤ N ′ .slot 16 if parent node.agent ̸ = 0 then 17 node.agent ← parent node.agent 18 node.slot ← parent node.slot 19 S ← S \ {node} 20 for node ∈ S s.t. node.type = AND do 21 if node.depth = 0 ∧ parent(node).agent ̸ = 0 then 22 node.agent ← parent(node).agent 23 node.slot ← parent(node).slot node.depth ̸ = 0 26 ∧∀ N ∈child(node) (N.agent ̸ = 0 ∨ N.depth = 0) then 27 child node ← N ∈ child (node) s.t. ∀ N ′ ∈child(node) N.slot ≥ N ′ .slot 28 node.agent ← child node.agent 29 node.slot ← child node.slot 30 S ← S \ {node} same agent and the same time slot as their parent if the parent is a SEQ node (l. 2-6).

Fig. 8 :

 8 Fig. 8: Treasure hunters: Assignment of Algorithm 3

Fig. 9 :

 9 Fig. 9: Scalability of different agent configurations

The authors acknowledge the support of CNRS and PAN, under the IEA project MoSART, and of NCBR Poland and FNR Luxembourg, under the PolLux/FNR-CORE project STV (POLLUX-VII/1/2019).