Lecture Formal methods in software engineering - Lecture 31 - TRƯỜNG CÁN BỘ QUẢN LÝ GIÁO DỤC THÀNH PHỐ HỒ CHÍ MINH
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (1.96 MB, 20 trang )
<span class='text_page_counter'>(1)</span><div class='page_container' data-page=1>
<i>Formal Methods in Software </i>
<i>Engineering </i>
</div>
<span class='text_page_counter'>(2)</span><div class='page_container' data-page=2>
<i>This Part</i>
<i>We apply the concepts, methods and tools you learnt to love in contexts that are </i>
<i>relatively close to what the people out there are facing. </i>
<i>In this lecture I show you what they are facing,</i>
<i>and I round off the entire lecture series.</i>
<i> </i>
</div>
<span class='text_page_counter'>(3)</span><div class='page_container' data-page=3>
<i>Contents of this lecture</i>
<i>A real application.</i>
<i>Testing based on formal methods.</i>
<i>Another real application.</i>
<i>Model construction and model checking</i>
</div>
<span class='text_page_counter'>(4)</span><div class='page_container' data-page=4></div>
<span class='text_page_counter'>(5)</span><div class='page_container' data-page=5>
<i>Nieuwe Waterweg Storm surge barrier</i>
<i> </i></div>
<span class='text_page_counter'>(6)</span><div class='page_container' data-page=6>
<i>First planned in 1953.</i>
<i>Completed in 1999.</i>
<i>Some statistical data:</i>
<i>Each barrier wall has the height of one Eifel </i>
<i>Tour, and weighs </i>
<i>twice as much.</i>
<i>Decision are taken 24 hrs before actual closure,</i>
<i>Reversible until 3 hrs before closure.</i>
<i>Fully mechanised software controlled </i>
<i>decision procedure.</i>
<i>Nieuwe Waterweg Storm surge barrier</i>
<i>(where ‘fully’ means </i>
<i><sub>FULLY’</sub></i>
<i><sub>FULLY</sub></i>
</div>
<span class='text_page_counter'>(7)</span><div class='page_container' data-page=7>
<i>Nieuwe Waterweg Storm surge barrier</i>
<i> </i><i>Rotterdam </i>
<i> </i><i>‘BESW’</i>
<i>‘BOS’</i>
<i>North Wall </i>
</div>
<span class='text_page_counter'>(8)</span><div class='page_container' data-page=8>
<i>The Storm surge barrier</i>
<i>System consists of</i>
<i> distributed components: </i>
<i> north wall,</i>
<i>south wall,</i>
<i>various hydraulic parts, engines, </i>
<i>etc.</i>
<i> BOS (‘beslissing & ondersteunend systeem’) </i>
<i>knows the environmental conditions;</i>
<i>takes decisions, based on the available data;</i>
<i>BESW (‘besturingssysteem waterweg’)</i>
</div>
<span class='text_page_counter'>(9)</span><div class='page_container' data-page=9></div>
<span class='text_page_counter'>(10)</span><div class='page_container' data-page=10>
<i>The Storm surge barrier</i>
<i>Budget issues</i>
<i>Total costs</i>
<i>> 500 million €;</i>
<i>Costs for software</i>
<i>< 10 million € (< 2%)</i>
<i>Control software (‘BBI’) developed mainly by </i>
<i>CMG.</i>
<i>Formal specification techniques used:</i>
<i> Z</i>
<i> Promela (academic SDL variant, nicer)</i>
<i>Experience (in a nutshell):</i>
</div>
<span class='text_page_counter'>(11)</span><div class='page_container' data-page=11>
<i>The Storm surge barrier</i>
<i>BBI main components</i>
<i>BOS </i>
<i>is informed every 10 minute </i>
<i>about water, wind and weather </i>
<i>status and forecast</i>
<i> computes anticipated water level;</i>
</div>
<span class='text_page_counter'>(12)</span><div class='page_container' data-page=12>
<i>The Storm surge barrier</i>
<i>BBI main components</i>
<i>BESW controls</i>
<i>water levels in docks;</i>
<i>opening/closing of dock gates;</i>
<i>moving of barrier walls;</i>
<i>sinking and refloating of </i>
<i>barrier walls;</i>
<i>…</i>
<i>BESW implements the BOS </i>
<i>instructions.</i>
</div>
<span class='text_page_counter'>(13)</span><div class='page_container' data-page=13>
<i>Some fragments of the BBI in SDL</i>
block BOS
BOS
[status,stop,close,…]
[data]
ENV
[curr]
BOS2BESW BESW2BOS
</div>
<span class='text_page_counter'>(14)</span><div class='page_container' data-page=14>
<i>BESW process fragment in SDL</i>
process BOS
S_active:=ff
S_ready :=tt
Closing
<i> </i>closed
FROM SOUTH
curr(active,ready,stopped)
<i>- </i>status <sub>FROM NORTH</sub><i> </i>closed
S_active
-N_active:=ff
N_ready :=tt
N_active
-active := S_-active && N_-active
ready := S_ready && N_ready
stopped:= S_stopped && N_stopped
<i>- </i>stop
S_active
S_active := ff
S_stopped:= tt
N_active
N_active := ff
N_stopped:= tt
…
…
tt
tt
ff
ff
DCL
</div>
<span class='text_page_counter'>(15)</span><div class='page_container' data-page=15>
<b></b>
-*
<i>BOS process fragments in SDL</i>
process BOS
Checking
status
Waiting
NONE
curr(active,ready,stopped)
Idle
close
Checking
data(…)
…
emergency
stop
</div>
<span class='text_page_counter'>(16)</span><div class='page_container' data-page=16>
<i>Problems?</i>
<i>Well, here is the intended </i>
<i>behaviour. </i>
<i>That’s how it should be.</i>
<i>Good!</i>
</div>
<span class='text_page_counter'>(17)</span><div class='page_container' data-page=17>
<i>BES W pr oc e s s f r a g m e nt in S DL</i>
process BOS
S_active:=ff
S_ready :=tt
Closing
closed
FROM SOUTH
curr(active,ready,stopped)
-status <sub>FROM NORTH</sub>closed
S_active
-N_active:=ff
N_ready :=tt
N_active
-active := S_-active && N_-active
ready := S_ready && N_ready
stopped:= S_stopped && N_stopped
stop
</div>
<span class='text_page_counter'>(18)</span><div class='page_container' data-page=18>
<i>Here is the (almost</i>
<i>) original MSC, </i>
<i>reported by Pim K</i>
<i>ars in November 1</i>
<i>998. </i>
<i>It was found with</i>
<i> the model checker </i>
</div>
<span class='text_page_counter'>(19)</span><div class='page_container' data-page=19></div>
<span class='text_page_counter'>(20)</span><div class='page_container' data-page=20>
<i>Storm surge barrier: Results</i>
<i>Z </i>
<i>was used for specifying the functions performed by processes; </i>
<i>syntax and typechecking was done with the ZTC tool;</i>
<i>was found </i>
<i>very useful</i>
<i>to allow a too great deal of freedom and </i>
<i>to offer little structure for the style in which it is to be used; </i>
</div>
<!--links-->
