Specifying Adaptive Program Behaviour Using Temporal Logic

Transcrição

Specifying Adaptive Program Behaviour
Using Temporal Logic
Based on the article “Using Temporal Logic to
Specify Adaptive Program Semantics”
by Ji Zhang and Betty H.C. Cheng
Michael Kruse
Fakultät für Elektrotechnik, Informatik und Mathematik an der Universität
Paderborn
Michael Kruse
Fakultät für Elektrotechnik, Informatik und Mathematik
Outline
1
Introduction
Motivation
Linear Temporal Logic
2
Model Checking of Adaptive Programs
Program Properties
Adapt-Operator Extended LTL
Adaptation Techniques
3
Discussion
Summary
Conclusion
2/31
Michael Kruse
Why Adaptive Software?
Software must react to changing conditions
e.g. Embedded software of an amphibious vehicle going into
the water
Software must cope with hardware malfunction
e.g. Loss of a harddisk in a RAID system
Software needs to change its behaviour according to these
changes
3/31
Michael Kruse
Program Representation
A program is list of statements that is ready to be executed
Suitable example: a Petri-Net
Example
A road where cars go from “On-Ramp” to “Off-Ramp”
On-Ramp
Off-Ramp
Ready transitions
On-Ramp → Off-Ramp
4/31
Michael Kruse
Example
A road where cars go from “On-Ramp” to “Off-Ramp”
On-Ramp
Off-Ramp
Ready transitions
4/31
Michael Kruse
Example
It is replaced by a detour around a construction site
Detour
On-Ramp
Off-Ramp
Ready transitions
On-Ramp → Detour
4/31
Michael Kruse
Example
Detour
On-Ramp
Off-Ramp
Ready transitions
On-Ramp → Detour
Detour → Off-Ramp
4/31
Michael Kruse
Example
Detour
On-Ramp
Off-Ramp
Ready transitions
On-Ramp → Detour
4/31
Michael Kruse
Example
Finally, the original road is restored
Detour
On-Ramp
Off-Ramp
Ready transitions
4/31
Michael Kruse
Example
Finally, the original road is restored
Detour
On-Ramp
Off-Ramp
Ready transitions
4/31
Michael Kruse
Why Model Checking?
Software is expected to work correct
In some systems even small errors may result in huge costs or
people being killed
e.g. First flight of Ariane 5, which exploded because of a small
software bug
Hence software is checked against its specification
5/31
Michael Kruse
Software Specification
Program: How software does something
By a sequence of instructions
Specification: What software is expected to do
Described by a Product Requirements Document
By Temporal Logic (e.g. Linear Temporal Logic)
Does a program fulfil its specification?
6/31
Michael Kruse
Linear Temporal Logic (LTL)
ϕ
X ϕ (next)
ϕ (always)
^ ϕ (eventually)
ϕ U ψ (until)
7/31
Michael Kruse
Properties for Adaptive Programs
Specification of a program can be described as a set of properties
that a program must fulfil.
Properties...
which ensure that nothing bad happens
⇒ Safety Properties
which ensure that something happens at all
⇒ Liveness Properties
that always hold, regardless which program is active
⇒ Global Invariants
8/31
Michael Kruse
Global Invariants
Some properties must always hold, regardless of the current
program state
Example
“Cars do not disappear, except at Off-Ramp”
∀c ∈ Cars : (c is not at Off-Ramp → X ∃R ∈ Road :
c is at R)
9/31
Michael Kruse
Global Invariants
Some properties must always hold, regardless of the current
program state
Example
“Cars do not disappear, except at Off-Ramp”
∀c ∈ Cars : (c is not at Off-Ramp → X ∃R ∈ Road :
c is at R)
Note: LTL does not support quantification (∀, ∃). Hence, these
must be expanded:
c1 is not at Off-Ramp → X (c1 is at R1 ) ∨ (c1 is at R2 ) ∨ . . .
∧ c2 is not at Off-Ramp → X (c2 is at R1 ) ∨ (c2 is at R2 ) ∨ . . . ∧ . . .
9/31
Michael Kruse
Point-Safety Properties
“Nothing bad may happen”
¬η
where η is a point formula
Example
“No car gets off the road”
¬ ∃c ∈ Cars, ∀R ∈ Road : c is not at R
|
{z
}
η
10/31
Michael Kruse
Point-Liveness Properties
“If something happens, the program must react”
(α → ^ β)
where α and β are point formulae
Example
“Every car at the On-Ramp reaches the Off-Ramp”
∀c ∈ Cars : (c is at On-Ramp → ^ c is at Off-Ramp)
|
{z
}
|
{z
}
α
β
11/31
Michael Kruse
The Adapt-Operator
We separate time into phases:
Source program phase: Before adaptation event (SSpec holds)
Target program phase: After adaptation event (TSpec holds)
Ω = (ΩS , ΩT ) holds during the transition
ΩS is a point-property that holds at the last state of the source
program phase
ΩT is a point-property that holds at the first state of the target
program phase
INV holds at both phases
global invariants (INV )
source program (SSpec ) Ω target program (TSpec )
ΩS
ΩT
12/31
Michael Kruse
Formal Definition (A-LTL)
Check existence of such phases by a new operator:
Ω
(ΩS ,ΩT )
SSpec * TSpec
Formal: SSpec * TSpec
holds in the infinite sequence (s0 , s1 , . . . ) iff there exists a state
si such that
SSpec holds in (s0 , s1 , . . . , si−1 , si , si , si , . . . )
TSpec holds in (si+1 , si+2 , si+3 , . . . )
ΩS holds at si
ΩT holds at si+1
ΩS
ΩT
13/31
Michael Kruse
Correctness for Point-Safety and Point-Liveness
(INV * INV ) ⇒ INV ?
Preservation of Point-Safety Properties
Let SSpec = TSpec = ¬η,
i.e. ( ¬η) * ( ¬η)
Then ¬η holds as a global invariant.
Preservation of Point-Liveness Properties
Let SSpec = TSpec = (α → ^ β),
i.e. (α → ^ β) * (α → ^ β)
Then (α → ^ β) holds as a global invariant.
14/31
Michael Kruse
Adaptation Techniques (Overview)
How to Change the Active Program
How to make the transition between two programs?
One-Point Adaptation
Guided Adaptation
Overlap Adaptation
15/31
Michael Kruse
Ω
SSpec ∧ ^ AReq * TSpec
AReq
Example
INV = ∀c ∈ Cars : (c at On-Ramp ⇒ ^ c at Off-Ramp)
(All cars eventually reach Off-Ramp)
SSpec = ∀c ∈ Cars : ¬(c not at On-Ramp ∧ c not at Off-Ramp)
(All cars are on the road)
AReq = Start of construction
TSpec = ∀c ∈ Cars : ¬(c not at On-Ramp ∧ c not at Off-Ramp ∧ c not at Detour)
(All cars are on the road or detour)
16/31
Michael Kruse
One-Point Adaptation (Example)
On-Ramp
Source Program
Off-Ramp
Formula
INV
Ω
Example
AReq
INV All cars reach Off-Ramp
SSpec All cars on road
AReq Start of construction
TSpec All cars on road or detour
17/31
Michael Kruse
On-Ramp
Source Program
Off-Ramp
Formula
INV
Ω
Example
AReq
17/31
Michael Kruse
On-Ramp
Source Program
Target Program
Off-Ramp
Detour
On-Ramp
Off-Ramp
Formula
INV
Ω
Example
AReq
17/31
Michael Kruse
On-Ramp
Source Program
Off-Ramp
m
n
adapt
Detour
Target Program
On-Ramp
m
n
Off-Ramp
Formula
INV
Ω
Example
AReq
17/31
Michael Kruse
On-Ramp
Source Program
Off-Ramp
m
n
adapt
Detour
Target Program
On-Ramp
m
n
Off-Ramp
Formula
INV
Ω
Example
AReq
17/31
Michael Kruse
Target Program
Detour
On-Ramp
Off-Ramp
Formula
INV
Ω
Example
AReq
17/31
Michael Kruse
Target Program
Detour
On-Ramp
Off-Ramp
Formula
INV
Ω
Example
AReq
17/31
Michael Kruse
Target Program
Detour
On-Ramp
Off-Ramp
Formula
INV
Ω
Example
AReq
17/31
Michael Kruse
Guided Adaptation
Ω1
SSpec ∧ ^ AReq * RCond
Ω2
* TSpec
Ω2 target program (TSpec )
source program (SSpec )
Ω1 restriction (R
Cond )
AReq
safe state
Example
INV = All cars eventually reach Off-Ramp
SSpec = All cars are on the road or detour
AReq = Construction finished
RCond = No car enters the detour
TSpec = All cars are on the road
18/31
Michael Kruse
Guided Adaptation (Example)
Source Program
Detour
On-Ramp
Off-Ramp
Formula
Ω1 restriction (R
INV
Ω2
Ω1
SSpec ∧ ^ AReq * RCond * TSpec
Cond )
Example
AReq
safe state
SSpec All cars on road or detour
AReq Construction finished
RCond No cars enter the detour
TSpec All cars on road
19/31
Michael Kruse
Source Program
Detour
On-Ramp
On-Ramp
Off-Ramp
Target Program
Off-Ramp
Formula
Ω1 restriction (R
INV
Ω2
Ω1
Cond )
Example
AReq
safe state
19/31
Michael Kruse
Source Program
Detour
On-Ramp
On-Ramp
Off-Ramp
Target Program
Off-Ramp
Formula
Ω1 restriction (R
INV
Ω2
Ω1
Cond )
Example
AReq
safe state
19/31
Michael Kruse
Source Program
Detour
On-Ramp
On-Ramp
Off-Ramp
Target Program
Off-Ramp
Formula
Ω1 restriction (R
INV
Ω2
Ω1
Cond )
Example
AReq
safe state
19/31
Michael Kruse
Source Program
Detour
On-Ramp
On-Ramp
Off-Ramp
Target Program
Off-Ramp
Formula
Ω1 restriction (R
INV
Ω2
Ω1
Cond )
Example
AReq
safe state
19/31
Michael Kruse
Detour
Source Program
On-Ramp
Off-Ramp
m
n
adapt
On-Ramp
Target Program m Off-Ramp
n
Formula
Ω1 restriction (R
INV
Ω2
Ω1
Cond )
Example
AReq
safe state
19/31
Michael Kruse
Detour
Source Program
On-Ramp
Off-Ramp
m
n
adapt
On-Ramp
Target Program m Off-Ramp
n
Formula
Ω1 restriction (R
INV
Ω2
Ω1
Cond )
Example
AReq
safe state
19/31
Michael Kruse
On-Ramp
Target Program
Off-Ramp
Formula
Ω1 restriction (R
INV
Ω2
Ω1
Cond )
Example
AReq
safe state
19/31
Michael Kruse
On-Ramp
Target Program
Off-Ramp
Formula
Ω1 restriction (R
INV
Ω2
Ω1
Cond )
Example
AReq
safe state
19/31
Michael Kruse
Overlap Adaptation
!
Ω2
Ω1
SSpec ∧ ^ AReq * RCond * true ∧
!
Ω1
Ω2
^ AReq * TSpec ∧ RCond * true
Ω2
Ω1 restriction (R
Cond )
AReq
restriction (RCond ) Ω
Ω1
2
target program (TSpec )
20/31
Michael Kruse
Overlap Adaptation (Example)
Source Program
Detour
On-Ramp
Off-Ramp
Formula
INV
Ω2
Ω1
SSpec ∧ ^ AReq * RCond * true
Ω1
Ω2
Ω2
Ω1 restriction (R
Cond )
Example
AReq
RCond No car enters the detour
TSpec No car off the road
21/31
Michael Kruse
Source Program
Detour
On-Ramp
Off-Ramp
Formula
INV
Ω2
Ω1
Ω1
Ω2
Ω2
Ω1 restriction (R
Cond )
Example
AReq
21/31
Michael Kruse
Detour
Overlap
On-Ramp
Off-Ramp
Formula
INV
Ω2
Ω1
Ω1
Ω2
Ω2
Ω1 restriction (R
Cond )
Example
AReq
21/31
Michael Kruse
Detour
Overlap
On-Ramp
Off-Ramp
Formula
INV
Ω2
Ω1
Ω1
Ω2
Ω2
Ω1 restriction (R
Cond )
Example
AReq
21/31
Michael Kruse
Detour
Overlap
On-Ramp
Off-Ramp
Formula
INV
Ω2
Ω1
Ω1
Ω2
Ω2
Ω1 restriction (R
Cond )
Example
AReq
21/31
Michael Kruse
Detour
Overlap
On-Ramp
Off-Ramp
Formula
INV
Ω2
Ω1
Ω1
Ω2
Ω2
Ω1 restriction (R
Cond )
Example
AReq
21/31
Michael Kruse
Target Program
On-Ramp
Off-Ramp
Formula
INV
Ω2
Ω1
Ω1
Ω2
Ω2
Ω1 restriction (R
Cond )
Example
AReq
21/31
Michael Kruse
Target Program
On-Ramp
Off-Ramp
Formula
INV
Ω2
Ω1
Ω1
Ω2
Ω2
Ω1 restriction (R
Cond )
Example
AReq
21/31
Michael Kruse
Summary
Adapt-Operator Extended LTL (A-LTL)
Program Properties
Global Invariants
Point-Safety Properties
Point-Liveness Properties
Adaptation Properties
Guided Adaptation
Overlap Adaptation
Expressiveness of LTL and A-LTL (Bonus)
22/31
Michael Kruse
Conclusion
Now we...
have a notation for program transitions (S * T )
defined different adaptation semantics
can check program phases independently using standard
model checking techniques
standard model checkers can be extended to verify adaptive
software systems as well
Deficiencies
Supports Point-Safety and Point-Liveness Properties only
Cyclic adaptations not possible as such
Adaption of Specification and Program may differ
Program state explosion
No implementation available
23/31
Michael Kruse
Any Questions?
?
24/31
Michael Kruse
A-LTL-Expressiveness
Point-Safety properties can be expressed with LTL only:
true
¬η * ψ ≡ (¬η) U ψ
Point-Liveness properties can be expressed in LTL only:
Determine every possible order of events (must be finite!)
Concatenate these events using the Until-Operator
Insert Globally-Properties
25/31
Michael Kruse
Adapt-Operator in LTL (I)
Example
( ¬η) ∧ (α → ^ β)
(ΩS ,ΩT )
*
ψ
The simplest case: ψ occurs in the first state
ΩT
ψ
ψ
26/31
Michael Kruse
Adapt-Operator in LTL (I)
Example
( ¬η) ∧ (α → ^ β)
(ΩS ,ΩT )
*
ψ
The simplest case: ψ occurs in the first state
ΩT
ψ
ΩT ∧ ψ
26/31
Michael Kruse
Adapt-Operator in LTL (II)
Example
( ¬η) ∧ (α → ^ β)
(ΩS ,ΩT )
*
ψ
The easy case: α does not occur
ΩS
¬α
ΩT
ψ
(¬α) U ψ
27/31
Michael Kruse
Adapt-Operator in LTL (II)
Example
( ¬η) ∧ (α → ^ β)
(ΩS ,ΩT )
*
ψ
The easy case: α does not occur
ΩS
¬α
ΩT
ψ
(¬α) U(¬α ∧ ΩS ∧ X(ΩS ∧ ψ))
27/31
Michael Kruse
Adapt-Operator in LTL (III)
Example
( ¬η) ∧ (α → ^ β)
(ΩS ,ΩT )
*
ψ
The general case: α must not occur after the last β
ΩS
β
¬α
ΩT
ψ
^(β ∧ X((¬α) U ψ))
28/31
Michael Kruse
Adapt-Operator in LTL (III)
Example
( ¬η) ∧ (α → ^ β)
(ΩS ,ΩT )
*
ψ
The general case: α must not occur after the last β
ΩS
β
¬α
ΩT
ψ
^(β ∧ X((¬α) U(¬α ∧ ΩS ∧ X(ΩT ∧ ψ))))
28/31
Michael Kruse
Adapt-Operator in LTL (IV)
Example
( ¬η) ∧ (α → ^ β)
(ΩS ,ΩT )
*
ψ
The special case: β holds in the last source state
ΩS
ΩT
β
ψ
^(β ∧ X ψ)
29/31
Michael Kruse
Adapt-Operator in LTL (IV)
Example
( ¬η) ∧ (α → ^ β)
(ΩS ,ΩT )
*
ψ
The special case: β holds in the last source state
ΩS
ΩT
β
ψ
^(β ∧ ΩS ∧ X(ΩT ∧ ψ))
29/31
Michael Kruse
Adapt-Operator in LTL (V)
Example
( ¬η) ∧ (α → ^ β)
(ΩS ,ΩT )
*
ψ
Until now we have
ΩT ∧ ψ
∨ (¬α) U(¬α ∧ ΩS ∧ X(ΩS ∧ ψ))
∨ ^(β ∧ X((¬α) U((¬α) ∧ ΩS ∧ X(ΩT ∧ ψ))))
∨ ^(β ∧ ΩS ∧ X(ωT ∧ ψ))
30/31
Michael Kruse
Example
( ¬η) ∧ (α → ^ β)
(ΩS ,ΩT )
*
ψ
When also considering ¬η
ΩT ∧ ψ
∨ (¬α ∧ ¬η) U(¬α ∧ ¬η ∧ ΩS ∧ X(ΩS ∧ ψ))
∨ (¬η) U(β ∧ ¬η ∧ X((¬α ∧ ¬η) U(¬α ∧ ¬η ∧ ΩS ∧ X(ΩT ∧ ψ))))
∨ (¬η) U(β ∧ ¬η ∧ ΩS ∧ X(ΩT ∧ ψ))
30/31
Michael Kruse
Example
( ¬η) ∧ (α → ^ β)
(ΩS ,ΩT )
*
ψ
When also considering ¬η
ΩT ∧ ψ
∨ (¬α ∧ ¬η) U(¬α ∧ ¬η ∧ ΩS ∧ X(ΩS ∧ ψ))
∨ (¬η) U(β ∧ ¬η ∧ X((¬α ∧ ¬η) U(¬α ∧ ¬η ∧ ΩS ∧ X(ΩT ∧ ψ))))
∨ (¬η) U(β ∧ ¬η ∧ ΩS ∧ X(ΩT ∧ ψ))
Ω
⇒ We stick to the ϕ * ψ syntax
30/31
Michael Kruse
Any Questions?
?
31/31

Specifying Adaptive Program Behaviour Using Temporal Logic

Transcrição

Documentos relacionados

Immediacy and Aesthetic Remediation in Television and Digital