/faculteit technologie management
Process Mining and Security:
Process Mining and Security:
Detecting Anomalous Process
Detecting Anomalous Process
Executions and Checking Process
Executions and Checking Process
Conformance
Conformance
Wil van der Aalst
Ana Karla A. de Medeiros
Eindhoven University of Technology
Department of Information and Technology
a.k.medeiros@tm.tue.nl
/faculteit technologie management
Outline
• Motivation
• Process Mining: -algorithm
• Detecting Anomalous Process Execution
• Checking Process Conformance
• Conclusion and Future work
/faculteit technologie management
Process Mining:
Overview
1) basic
performance
metrics
2) process model
Start
Register order
Prepare
shipment
Ship goods
(Re)send bill
Receive payment
C ontact
customer
Archive order
End
3) organizational model
4) social network
5)
performance
characteristics
If …then …
6) auditing/security
/faculteit technologie management
– Workflow
Mining (What is
the process?)
– Delta analysis
(Are we doing
what was
specified?)
– Performance
analysis
(How can we
improve?)
Motivation
/faculteit technologie management
Motivation
How can we benefit from process
How can we benefit from process
mining to verify security issues in
mining to verify security issues in
computer systems?
computer systems?
– Detect anomalous process
execution
– Check process conformance
/faculteit technologie management
Process Mining –
Process log
ABCD
ABCD
ACBD
ACBD
EF
EF
case 1 : task A
case 1 : task A
case 2 : task A
case 2 : task A
case 3 : task A
case 3 : task A
case 3 : task B
case 3 : task B
case 1 : task B
case 1 : task B
case 1 : task C
case 1 : task C
case 2 : task C
case 2 : task C
case 4 : task A
case 4 : task A
case 2 : task B
case 2 : task B
case 2 : task D
case 2 : task D
case 5 : task E
case 5 : task E
case 4 : task C
case 4 : task C
case 1 : task D
case 1 : task D
case 3 : task C
case 3 : task C
case 3 : task D
case 3 : task D
case 4 : task B
case 4 : task B
case 5 : task F
case 5 : task F
case 4 : task D
case 4 : task D
• Minimal information in
noise-free log: case id’s
and task id’s
• Additional information:
event type, time,
resources, and data
• In this log there are three
possible sequences:
/faculteit technologie management
Process Mining –
Ordering Relations >,,||,#
• Direct
succession: x>y
iff for some case x
is directly followed
by y.
• Causality: xy iff
x>y and not y>x.
• Parallel: x||y iff
x>y and y>x
• Unrelated: x#y iff
not x>y and not
y>x.
case 1 : task A
case 1 : task A
case 2 : task A
case 2 : task A
case 3 : task A
case 3 : task A
case 3 : task B
case 3 : task B
case 1 : task B
case 1 : task B
case 1 : task C
case 1 : task C
case 2 : task C
case 2 : task C
case 4 : task A
case 4 : task A
case 2 : task B
case 2 : task B
...
...
A>B
A>B
A>C
A>C
B>C
B>C
B>D
B>D
C>B
C>B
C>D
C>D
E>F
E>F
A
A
B
B
A
A
C
C
B
B
D
D
C
C
D
D
E
E
F
F
B||C
B||C
C||B
C||B
ABCD
ABCD
ACBD
ACBD
EF
EF
/faculteit technologie management
Process Mining –
-algorithm
Let W be a workflow log over T. (W) is defined as follows.
1.T
W
= { t T
W
t },
2.T
I
= { t T
W
t = first() },
3.T
O
= { t T
W
t = last() },
4.X
W
= { (A,B) A T
W
B T
W
a A
b B
a
W
b
a1,a2 A
a
1
#
W
a
2
b1,b2 B
b
1
#
W
b
2
},
5.Y
W
= { (A,B) X
(A,B) X
A A B B (A,B) = (A,B) },
6.P
W
= { p
(A,B)
(A,B) Y
W
} {i
W
,o
W
},
7.F
W
= { (a,p
(A,B)
) (A,B) Y
W
a A } { (p
(A,B)
,b) (A,B)
Y
W
b B } { (i
W
,t) t T
I
} { (t,o
W
) t T
O
}, and
.
8 (W) = (P
W
,T
W
,F
W
).
/faculteit technologie management
Process Mining –
-algorithm
A
B
C
D
E
F
ABCD
ABCD
ACBD
ACBD
EF
EF
A
A
B
B
A
A
C
C
B
B
D
D
C
C
D
D
E
E
F
F
B||C
B||C
C||B
C||B
/faculteit technologie management
Process Mining –
-algorithm
• If log is complete with respect to relation >, it
can be used to mine SWF-net without short loops
• Structured Workflow Nets (SWF-nets) have no
implicit places and the following two constructs
cannot be used:
/faculteit technologie management
Detecting Anomalous
Process Executions
• Use the
-algorithm to discover the
acceptable behavior
– Log traces = audit trails
– Cases = session ids
– Complete log only has acceptable audit trails
• Verify the conformance of new audit trails
by playing the “token game”
/faculteit technologie management
Detecting Anomalous
Process Executions
Enter, Select Product, Add to Basket, Cancel
Order
/faculteit technologie management
Detecting Anomalous
Process Executions
Enter, Select Product, Add to Basket, Proceed
to Checkout, Fill in Delivery Info, Fill in
Payment Info, Process Order, Finish Checkout
/faculteit technologie management
• Verify if a
pattern holds
Checking Process
Conformance
Provide
Password
Process Order
So…
Provide Password > Process Order
and
NOT Process Order > Provide Password
/faculteit technologie management
Provide Password Process Order
Checking Process
Conformance
(!) Token game can be used to verify if the
pattern holds
for every audit trail
/faculteit technologie management
Conclusion
– Process mining can be used to
• Detect anomalous behavior
• Check process conformance
– Tools are available at our website
www.processmining.org
www.processmining.org
Future Work
– Apply process mining to audit trails from real-life
case studies
Conclusion and
Future Work
/faculteit technologie management
Questions?
www.processmining.org
www.processmining.org