README.md 7.86 KB
Newer Older
Jaime Arias's avatar
Jaime Arias committed
1
2
3
4
5
6
7
8
9
10
11
# Minimal Schedule with Minimal Number of Agents in Attack-Defence Trees

This repository hosts the results for the paper.

## Clone this repository:
```
git clone https://depot.lipn.univ-paris13.fr/parties/publications/minimal-scheduling.git && cd minimal-scheduling
```

## Folder Structure

Jaime Arias's avatar
Jaime Arias committed
12
13
```
.
Jaime Arias's avatar
Jaime Arias committed
14
├── results # folder with the ADTree models and the minimal assignments
Jaime Arias's avatar
Jaime Arias committed
15
16
├── script  # folder with the scripts to generate the scalability results
└── tool #  # folder with the binaries of the tool adt2amas
Jaime Arias's avatar
Jaime Arias committed
17
18
```

Jaime Arias's avatar
Jaime Arias committed
19
20
## Results

Jaime Arias's avatar
Jaime Arias committed
21
22
23
The minimal scheduling results can be found in the `results` folder. The
reader can found the sources and binaries of the `adt2amas` tool
[here](https://depot.lipn.univ-paris13.fr/parties/tools/adt2amas/-/releases/v2.1.2).
Jaime Arias's avatar
Jaime Arias committed
24
25
26
27
28
In order to reproduce the results, the command to be executed is the following :
```
./adt2amas minimal --model results/<case_study>/model/<case_study>.txt
```

Jaime Arias's avatar
Jaime Arias committed
29
Below we show some case studies.
30

Jaime Arias's avatar
Jaime Arias committed
31
32
33
34
35
36
37
38
39
- [Forestalling a software release (forestall)](#forestalling-a-software-release-forestall)
- [Obtain admin privileges (gain-admin)](#obtain-admin-privileges-gain-admin)
- [Interrupted](#interrupted)
- [Compromise IoT device (iot-dev)](#compromise-iot-device-iot-dev)
- [Last](#last)
- [Example from [5]](#example-from-5)
- [Treasure Hunters](#treasure-hunters)
- [Scaling Example](#scaling-example)

40
41
42
43
44
45
46
47
### Forestalling a software release (forestall)

This model is based on a real-world instance [1]. It models an attack
to the intellectual property of a company C, by an unlawful competitor
company U aiming at being “first to the market.” Following [2],
software extraction from C takes place before U builds it into its own
product, and U must deploy to market before C, which takes place after U has
integrated the stolen software into its product.
Jaime Arias's avatar
Jaime Arias committed
48
49
50
51
52
53
54

#### ADTree model

![forestall ADTree](results/forestall/model/forestall.png)

#### Minimal Scheduling

Jaime Arias's avatar
Jaime Arias committed
55
The reader can find the 4 possible assignments [here](results/forestall/assignment).
Jaime Arias's avatar
Jaime Arias committed
56

57
58
59
60
61
62
63
### Obtain admin privileges (gain-admin)

To gain administrative privileges in a UNIX system, an attacker needs either
physical access to an already logged-in console or remote access via
privilege escalation (attacking SysAdmin). This case study [3] exhibits a
mostly branching structure: all gates but one are disjunctions in the
original tree of [3]. We enrich this scenario with the SAND gates of [2],
Jaime Arias's avatar
Jaime Arias committed
64
and further add reactive defences.
Jaime Arias's avatar
Jaime Arias committed
65
66
67
68
69
70
71

#### ADTree model

![gain-admin ADTree](results/gain-admin/model/gain-admin.png)

#### Minimal Scheduling

Jaime Arias's avatar
Jaime Arias committed
72
The reader can find the 16 possible assignments [here](results/gain-admin/assignment).
Jaime Arias's avatar
Jaime Arias committed
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

### Interrupted

#### ADTree model

![interrupted ADTree](results/interrupted/model/interrupted.png)

#### Minimal Scheduling

![interrupted Assignment](results/interrupted/assignment/interrupted_scheduling_1.png)

### Compromise IoT device (iot-dev)

This model describes an attack to an Internet-of-Things (IoT) device either
via wireless or wired LAN. Once the attacker gains access to the private
network and has acquired the corresponding credentials, it can exploit a
software vulnerability in the IoT device to run a malicious script. Our
ADTree adds defence nodes on top of the attack trees used in [4].

#### ADTree model

![iot-dev ADTree](results/iot-dev/model/iot-dev.png)

#### Minimal Scheduling

Jaime Arias's avatar
Jaime Arias committed
98
![iot-dev Assignment](results/iot-dev/assignment/iot_dev_scheduling_1.png)
Jaime Arias's avatar
Jaime Arias committed
99
100
101
102
103
104
105
106
107
108
109

### Last

#### ADTree model

![last ADTree](results/last/model/last.png)

#### Minimal Scheduling

![last Assignment](results/last/assignment/last_scheduling_1.png)

Jaime Arias's avatar
Jaime Arias committed
110
### Example from [5]
Jaime Arias's avatar
Jaime Arias committed
111
112
113
114
115
116
117
118
119

#### ADTree model

![toy-example ADTree](results/toy-example/model/toy-example.png)

#### Minimal Scheduling

![toy-example Assignment](results/toy-example/assignment/toy_example_scheduling_1.png)

Jaime Arias's avatar
Jaime Arias committed
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
### Treasure Hunters

It models thieves that try to steal a treasure in a museum. To achieve their
goal, they first must access the treasure room, which involves bribing a
guard (b), and forcing the secure door (f). Both actions are costly and take
some time. Two coalitions are possible: either a single thief has to carry
out both actions, or a second thief could be hired to parallelise b and f.
After these actions succeed the attacker/s can steal the treasure (ST), which
takes a little time for opening its display stand and putting it in a bag. If
the two-thieves coalition is used, we encode in ST an extra 90 € to hire the
second thief — the computation function of the gate can handle this plurality
— else ST incurs no extra cost. Then the thieves are ready to flee (TF),
choosing an escape route to get away (GA): this can be a spectacular escape
in a helicopter (h), or a mundane one via the emergency exit (e). The
helicopter is expensive but fast while the emergency exit is slower but at no
cost. Furthermore, the time to perform a successful escape could depend on
the number of agents involved in the robbery. Again, this can be encoded via
computation functions in gate GA.

As soon as the treasure room is penetrated (i.e. after b and f but before ST)
an alarm goes off at the police station, so while the thieves flee the police
hurries to intervene (p). The treasure is then successfully stolen iff the
thieves have fled and the police failed to arrive or does so too late. This
last possibility is captured by the condition associated with the treasure
stolen gate (TS), which states that the arrival time of the police must be
greater than the time for the thieves to steal the treasure and go away.

Jaime Arias's avatar
Jaime Arias committed
147
148
#### ADTree model

Jaime Arias's avatar
Jaime Arias committed
149
150
![Treasure Hunters ADTree](results/treasure-hunters/model/treasure-hunters.png)

Jaime Arias's avatar
Jaime Arias committed
151
#### Minimal Scheduling
152

Jaime Arias's avatar
Jaime Arias committed
153
154
![Treasure Hunters Assignment](results/treasure-hunters/assignment/treasure_hunters_scheduling_1.png)

Jaime Arias's avatar
Jaime Arias committed
155
### Scaling Example
156

Jaime Arias's avatar
Jaime Arias committed
157
158
#### ADTree model

Jaime Arias's avatar
Jaime Arias committed
159
![tricky ADTree](results/tricky/model/tricky.png)
Jaime Arias's avatar
Jaime Arias committed
160

Jaime Arias's avatar
Jaime Arias committed
161
#### Minimal Scheduling
Jaime Arias's avatar
Jaime Arias committed
162

Jaime Arias's avatar
Jaime Arias committed
163
![tricky Assignment](results/tricky/assignment/tricky_scheduling_1.png)
Jaime Arias's avatar
Jaime Arias committed
164

Jaime Arias's avatar
Jaime Arias committed
165
166
167
168
#### Scalability Results

![tricky Assignment](script/scalability.png)

Jaime Arias's avatar
Jaime Arias committed
169
170
171
## Authors

- Jaime Arias (LIPN, CNRS UMR 7030, Université Sorbonne Paris Nord)
Jaime Arias's avatar
Jaime Arias committed
172
- Łukasz Maśko (Institute of Computer Science, PAS, Warsaw University of Technology)
Jaime Arias's avatar
Jaime Arias committed
173
174
175
176
- Wojciech Penczek (Institute of Computer Science, PAS, Warsaw University of Technology)
- Laure Petrucci (LIPN, CNRS UMR 7030, Université Sorbonne Paris Nord)
- Teofil Sidoruk (Institute of Computer Science, PAS, Warsaw University of Technology)

Jaime Arias's avatar
Jaime Arias committed
177
## Abstract
178

Jaime Arias's avatar
Jaime Arias committed
179
180
181
182
183
184
185
186
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.
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
## References

[1] A. Buldas, P. Laud, J. Priisalu, M. Saarepera, and J. Willemson. Rational
Choice of Security Measures Via Multi-parameter Attack Trees. In Critical
Information Infrastructures Security, pages 235–248. Springer, 2006.

[2] R. Kumar, E. Ruijters, and M. Stoelinga. Quantitative attack tree analysis
via priced timed automata. In FORMATS 2015, volume 9268 of LNCS, pages 156–
171. Springer, 2015.

[3] J. D. Weiss. A system security engineering process. In Proceedings of the
14th National Computer Security Conference, pages 572–581, 1991.

[4] R. Kumar, S. Schivo, E. Ruijters, B. M. Yildiz, D. Huistra, J. Brandt, A.
Rensink, and M. Stoelinga. Effective analysis of attack trees: A model-driven
approach. In Fundamental Approaches to Software Engineering, pages 56–73.
Springer, 2018.

Jaime Arias's avatar
Jaime Arias committed
205
206
207
208
[5] J. Arias, C. E. Budde, W. Penczek, L. Petrucci, T. Sidoruk, and M.
Stoelinga. Hackers vs. Security: Attack-Defence Trees as Asynchronous
Multi-agent Systems. In Formal Methods and Software Engineering, vol. 12531,
pages 3-19. Springer, 2020.