/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

[e-mail]

/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: xy 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