Share
Embed
VeriFast Termination Checking Introduction(α)
静的コード解析の会 第2回 (https://metasepi.connpass.com/event/50450/) で発表した資料です。
VeriFastによるC(およびJava)言語の停止性証明に関する解説を行っています。停止性検査を行う理論的背景を説明し、これを行う際にVeriFastの採る大まかな方針と検証のアイデアを説明しています。
eldesh
April 29, 2017
Transcript
50 slides
-
࣍ VeriFast ֓આ ఀࢭੑݕࠪͱԿ͔ ఀࢭੑݕࠪ͜ͱ͡Ί Ұൠͷ߹ͷఀࢭੑݕࠪ ύλʔϯผఀࢭੑݕূ ࢀর VeriFast Termination
Checking Introduction(α) @eldesh https://twitter.com/eldesh http://d.hatena.ne.jp/eldesh ੩తίʔυղੳͷձ ୈ 2 ճ 2017/04/29 2017/04/29 VeriFast Termination Checking 1 / 42 -
࣍ VeriFast ֓આ ఀࢭੑݕࠪͱԿ͔ ఀࢭੑݕࠪ͜ͱ͡Ί Ұൠͷ߹ͷఀࢭੑݕࠪ ύλʔϯผఀࢭੑݕূ ࢀর ࣍ 1
VeriFast ֓આ 2 ఀࢭੑݕࠪͱԿ͔ 3 ఀࢭੑݕࠪ͜ͱ͡Ί 4 Ұൠͷ߹ͷఀࢭੑݕࠪ 5 ύλʔϯผఀࢭੑݕূ 6 ࢀর 2017/04/29 VeriFast Termination Checking 2 / 42 -
࣍ VeriFast ֓આ ఀࢭੑݕࠪͱԿ͔ ఀࢭੑݕࠪ͜ͱ͡Ί Ұൠͷ߹ͷఀࢭੑݕࠪ ύλʔϯผఀࢭੑݕূ ࢀর What is
this slide? ͜ͷεϥΠυͰ VeriFast ʹΑΔ C ݴޠϓϩάϥϜͷఀࢭੑݕূͷํ๏ͱɺ ͦͷػೳͷجૅͱͳΔ֓೦ʹ͍ͭͯհ͠·͢ 1ɻ 1Java Ͱશ͘ಉ༷ͷߟ͑ํͰݕূग़དྷ·͢ 2017/04/29 VeriFast Termination Checking 3 / 42 -
࣍ VeriFast ֓આ ఀࢭੑݕࠪͱԿ͔ ఀࢭੑݕࠪ͜ͱ͡Ί Ұൠͷ߹ͷఀࢭੑݕࠪ ύλʔϯผఀࢭੑݕূ ࢀর ఆ/ରௌऺ ඞਢ
C ݴޠ͕͔Δ ·͍͠ ࣄલ/ࣄޙ݅ͷݕ͕ࠪͲΜͳͷͳͷ͔͔Δ 2017/04/29 VeriFast Termination Checking 4 / 42 -
࣍ VeriFast ֓આ ఀࢭੑݕࠪͱԿ͔ ఀࢭੑݕࠪ͜ͱ͡Ί Ұൠͷ߹ͷఀࢭੑݕࠪ ύλʔϯผఀࢭੑݕূ ࢀর ఀࢭੑݕࠪͱ ϓϩάϥϜ͕
(༗ݶ࣌ؒʹ) ఀࢭ͢Δ͜ͱΛݕࠪ͢Δ͜ͱɻ 2017/04/29 VeriFast Termination Checking 5 / 42 -
࣍ VeriFast ֓આ ఀࢭੑݕࠪͱԿ͔ ఀࢭੑݕࠪ͜ͱ͡Ί Ұൠͷ߹ͷఀࢭੑݕࠪ ύλʔϯผఀࢭੑݕূ ࢀর VeriFast ͕ݕࠪ͢Δ͜ͱ
ͱ͜ΖͰɺVeriFast ϓϩάϥϜ (ؔ) ͱɺͦͷࣄલ݅/ࣄޙ݅ͱͷҰ ؏ੑΛݕࠪ͢Δɻ 2017/04/29 VeriFast Termination Checking 6 / 42 -
࣍ VeriFast ֓આ ఀࢭੑݕࠪͱԿ͔ ఀࢭੑݕࠪ͜ͱ͡Ί Ұൠͷ߹ͷఀࢭੑݕࠪ ύλʔϯผఀࢭੑݕূ ࢀর VeriFast ͕ݕࠪ͢Δ͜ͱ
ͱ͜ΖͰɺVeriFast ϓϩάϥϜ (ؔ) ͱɺͦͷࣄલ݅/ࣄޙ݅ͱͷҰ ؏ੑΛݕࠪ͢Δɻ ⇒ ͜ΕԿ͕ݕূग़དྷ͍ͯΔͷ͔ɻ 2017/04/29 VeriFast Termination Checking 6 / 42 -
࣍ VeriFast ֓આ ఀࢭੑݕࠪͱԿ͔ ఀࢭੑݕࠪ͜ͱ͡Ί Ұൠͷ߹ͷఀࢭੑݕࠪ ύλʔϯผఀࢭੑݕূ ࢀর VeriFast Ͱݕࠪͨؔ͠
ΤϯΩϡʔͷ༷ͷྫ void enqueue(struct queue *q, int x) //@ requires queue(q, ?vs); //@ ensures queue(q, iappend(vs , icons(x, inil ))); { ... } 2017/04/29 VeriFast Termination Checking 7 / 42 -
࣍ VeriFast ֓આ ఀࢭੑݕࠪͱԿ͔ ఀࢭੑݕࠪ͜ͱ͡Ί Ұൠͷ߹ͷఀࢭੑݕࠪ ύλʔϯผఀࢭੑݕূ ࢀর Hoare triple
ؔͱɺͦͷࣄલ݅/ࣄޙ݅ 3 ͭΛ߹Θͤͯ Hoare triple ͱݺͿɻ ͜ΕΛܗࣜతʹѻ͏ࡍʹҎԼͷΑ͏ʹදه͢Δɻ Hoare triple ⊢ {P} c {Q} 2017/04/29 VeriFast Termination Checking 8 / 42 -
࣍ VeriFast ֓આ ఀࢭੑݕࠪͱԿ͔ ఀࢭੑݕࠪ͜ͱ͡Ί Ұൠͷ߹ͷఀࢭੑݕࠪ ύλʔϯผఀࢭੑݕূ ࢀর Hoare triple
ͷҙຯ ؔͱɺͦͷࣄલ݅/ࣄޙ݅ 3 ͭΛ߹Θͤͯ Hoare triple ͱݺͿɻ Hoare triple ͷҙຯ ⊢ {P} c {Q} ⇔ ∀h, γ.Ifix , h |= P ∧ (h, c) ⇓ γ ⇒ γ |= Q γ |= Q ͷҙຯ Divergence |= Q Ifix , h |= Q[v/res] (n, v, h) |= Q Divergence ൃࢄͨ͠ঢ়ଶ (ແݶϧʔϓ) Λද͢ɻ 2017/04/29 VeriFast Termination Checking 9 / 42 -
࣍ VeriFast ֓આ ఀࢭੑݕࠪͱԿ͔ ఀࢭੑݕࠪ͜ͱ͡Ί Ұൠͷ߹ͷఀࢭੑݕࠪ ύλʔϯผఀࢭੑݕূ ࢀর Hoare triple
ͷҙຯ Divergence |= Q ͱ͍͏͜ͱɺແݶϧʔϓʹͳͬͨ߹ৗʹ Q ࣄޙ ͕݅Γཱͭͱݴ͍ͬͯΔɻ 2017/04/29 VeriFast Termination Checking 10 / 42 -
࣍ VeriFast ֓આ ఀࢭੑݕࠪͱԿ͔ ఀࢭੑݕࠪ͜ͱ͡Ί Ұൠͷ߹ͷఀࢭੑݕࠪ ύλʔϯผఀࢭੑݕূ ࢀর Hoare triple
ͷҙຯ Divergence |= Q ͱ͍͏͜ͱɺແݶϧʔϓʹͳͬͨ߹ৗʹ Q ࣄޙ ͕݅Γཱͭͱݴ͍ͬͯΔɻ ⇒VerifFast ແݶϧʔϓʹͳΔ͔Ͳ͏͔ݕূ͠ͳ͍ 2017/04/29 VeriFast Termination Checking 10 / 42 -
࣍ VeriFast ֓આ ఀࢭੑݕࠪͱԿ͔ ఀࢭੑݕࠪ͜ͱ͡Ί Ұൠͷ߹ͷఀࢭੑݕࠪ ύλʔϯผఀࢭੑݕূ ࢀর Hoare triple
ͷҙຯ VeriFast ෦ਖ਼ੑ (partial correctness) Λ࣋ͭɻ ෦ਖ਼ੑ ϓϩάϥϜͷ࣮ߦ݁Ռ͕ग़ͨ (=ਖ਼͘͠ऴྃͨ͠) ߹ʹ ͦͷਖ਼͠͞Λอূ͢Δ ⇕ Partial Correctness ͜Εʹରͯ͠ɺৗʹϓϩάϥϜ͕ਖ਼͍݁͠ՌΛग़ྗ͢Δ߹ɺ͜ΕΛશ ਖ਼ੑ (Total Correctness) Λ࣋ͭ ͱ͍͏ɻ 2017/04/29 VeriFast Termination Checking 11 / 42 -
࣍ VeriFast ֓આ ఀࢭੑݕࠪͱԿ͔ ఀࢭੑݕࠪ͜ͱ͡Ί Ұൠͷ߹ͷఀࢭੑݕࠪ ύλʔϯผఀࢭੑݕূ ࢀর ఀࢭੑݕࠪͱ (࠶)
࠶ ϓϩάϥϜ͕ (༗ݶ࣌ؒʹ) ఀࢭ͢Δ͜ͱΛݕࠪ͢Δ͜ͱɻ ͱ͍͏͜ͱ. . . ఀࢭੑΛݕূ͢Δ ⇕ VeriFast ʹશਖ਼ੑΛ༩͑Δ ⇕ ϓϩάϥϜ͕ৗʹਖ਼͍͑͠Λฦ͢͜ͱΛอূͰ͖Δ 2017/04/29 VeriFast Termination Checking 12 / 42 -
࣍ VeriFast ֓આ ఀࢭੑݕࠪͱԿ͔ ఀࢭੑݕࠪ͜ͱ͡Ί Ұൠͷ߹ͷఀࢭੑݕࠪ ύλʔϯผఀࢭੑݕূ ࢀর ఀࢭੑݕࠪͷࢦఆ ؔͷఀࢭੑΛݕࠪ͢Δʹ௨ৗͷࣄલ,
ࣄޙ݅ͷଞʹ terminates Λࢦ ఆ͢Δ. Կ͠ͳ͍ؔͷݕূ void empty_cmd (void) //@ requires emp; //@ ensures emp; //@ terminates; { } 2017/04/29 VeriFast Termination Checking 13 / 42 -
࣍ VeriFast ֓આ ఀࢭੑݕࠪͱԿ͔ ఀࢭੑݕࠪ͜ͱ͡Ί Ұൠͷ߹ͷఀࢭੑݕࠪ ύλʔϯผఀࢭੑݕূ ࢀর ࣗ໌ʹఀࢭ͢Δྫ 1
ϓϦϛςΟϒͳԋࢉࣗ໌ʹఀࢭ͢Δɻ less than ͷ༷ bool compare (int x, int y) //@ requires emp; //@ ensures result == (x < y); //@ terminates; { return x < y; // ฦΓେখൺֱͷ݁ՌʹҰக͢Δ } 2017/04/29 VeriFast Termination Checking 14 / 42 -
࣍ VeriFast ֓આ ఀࢭੑݕࠪͱԿ͔ ఀࢭੑݕࠪ͜ͱ͡Ί Ұൠͷ߹ͷఀࢭੑݕࠪ ύλʔϯผఀࢭੑݕূ ࢀর ࣗ໌ʹఀࢭ͢Δྫ 2
if จࣗ໌ʹఀࢭ͢Δɻ if statement int max_int (int x, int y) //@ requires emp; //@ ensures result == (x > y ? x : y); //@ terminates; { if (x > y) { return x; } else { return y; } } 2017/04/29 VeriFast Termination Checking 15 / 42 -
࣍ VeriFast ֓આ ఀࢭੑݕࠪͱԿ͔ ఀࢭੑݕࠪ͜ͱ͡Ί Ұൠͷ߹ͷఀࢭੑݕࠪ ύλʔϯผఀࢭੑݕূ ࢀর ࣗ໌ʹఀࢭ͢Δྫ 3
ఀࢭ͢ΔؔΛݺͿؔఀࢭ͢Δ͜ͱ͕ࣗಈͰݕࠪͰ͖Δɻ call function int callee (int x) //@ requires emp; //@ ensures emp; //@ terminates; { return 0; } void caller (void) //@ requires emp; //@ ensures emp; //@ terminates; { callee (3); } 2017/04/29 VeriFast Termination Checking 16 / 42 -
࣍ VeriFast ֓આ ఀࢭੑݕࠪͱԿ͔ ఀࢭੑݕࠪ͜ͱ͡Ί Ұൠͷ߹ͷఀࢭੑݕࠪ ύλʔϯผఀࢭੑݕূ ࢀর ఀࢭ͢Δϧʔϓ ϧʔϓΠϯόϦΞϯτʹՃ͑ͯɺݮগ͢ΔύϥϝʔλΛࢦఆ͢Δ͜ͱͰఀ
ࢭ͢Δ͜ͱ͕อোͰ͖Δɻ while loop void loop (int x) //@ requires 0 < x; //@ ensures emp; //@ terminates; { int i = 0; while (i < x) //@ invariant i <= x; //@ decreases x - i; { ++i; } } 2017/04/29 VeriFast Termination Checking 17 / 42 -
࣍ VeriFast ֓આ ఀࢭੑݕࠪͱԿ͔ ఀࢭੑݕࠪ͜ͱ͡Ί Ұൠͷ߹ͷఀࢭੑݕࠪ ύλʔϯผఀࢭੑݕূ ࢀর ࣗ໌Ͱͳ͍ఀࢭ͢Δྫ ΞοΧʔϚϯؔ
int ackermann(int m, int n) { if (m == 0) { return n + 1; } else { if (n == 0) { int r = ackermann(m - 1, 1); return r; } else { return ackermann(m - 1, ackermann(m, n - 1)); } } } ఀࢭੑΛݕূͨ͠ίʔυ examples/termination/ackermann.c Λࢀরɻ72 ߦ͋Δɻ 2017/04/29 VeriFast Termination Checking 18 / 42 -
࣍ VeriFast ֓આ ఀࢭੑݕࠪͱԿ͔ ఀࢭੑݕࠪ͜ͱ͡Ί Ұൠͷ߹ͷఀࢭੑݕࠪ ύλʔϯผఀࢭੑݕূ ࢀর جຊతͳൃ શͯͷݺͼग़͠γʔέϯε͕༗ݶεςοϓ͔͠ͳ͍͜ͱΛࣔͤྑ͍ɻ
⇒ Ͳ͏͢Δ͔ 2017/04/29 VeriFast Termination Checking 19 / 42 -
࣍ VeriFast ֓આ ఀࢭੑݕࠪͱԿ͔ ఀࢭੑݕࠪ͜ͱ͡Ί Ұൠͷ߹ͷఀࢭੑݕࠪ ύλʔϯผఀࢭੑݕূ ࢀর fixpoint ͱ͜ΖͰ
VeriFast ໋தͷؔΛ fixpoint ͱ͍͏ΩʔϫʔυͰهड़͢Δ ͜ͱ͕ग़དྷΔɻ fixpoint ؔͷྫ fixpoint int length <t>(list <t> xs) { switch (xs) { case nil: return 0; case cons(x, xs0): return 1 + length(xs0); } } 2017/04/29 VeriFast Termination Checking 20 / 42 -
࣍ VeriFast ֓આ ఀࢭੑݕࠪͱԿ͔ ఀࢭੑݕࠪ͜ͱ͡Ί Ұൠͷ߹ͷఀࢭੑݕࠪ ύλʔϯผఀࢭੑݕূ ࢀর fixpoint fixpoint
ඞͣఀࢭ͢Δɻ fixpoint ؔͷྫ fixpoint int length <t>(list <t> xs) { switch (xs) { case nil: return 0; case cons(x, xs0): return 1 + length(xs0); } } 2017/04/29 VeriFast Termination Checking 20 / 42 -
࣍ VeriFast ֓આ ఀࢭੑݕࠪͱԿ͔ ఀࢭੑݕࠪ͜ͱ͡Ί Ұൠͷ߹ͷఀࢭੑݕࠪ ύλʔϯผఀࢭੑݕূ ࢀর fixpoint fixpoint
ͳͥඞͣఀࢭ͢Δͷ͔ fixpoint ؔͷྫ fixpoint int length <t>(list <t> xs) { switch (xs) { case nil: return 0; case cons(x, xs0): return 1 + length(xs0); } } 2017/04/29 VeriFast Termination Checking 20 / 42 -
࣍ VeriFast ֓આ ఀࢭੑݕࠪͱԿ͔ ఀࢭੑݕࠪ͜ͱ͡Ί Ұൠͷ߹ͷఀࢭੑݕࠪ ύλʔϯผఀࢭੑݕূ ࢀর fixpoint ͷ੍ݶ
fixpoint ʹΑΔؔͷఆٛʹɺҙͷ͕ؔهड़Ͱ͖ΔΘ͚Ͱͳ͘ز ੍͔͕ͭ͏ 2ɻ fixpoint ͷ੍ݶ ୯ಠͷ return ·ͨ switch จͰ͋Δ͜ͱ switch ʹͤΔͷ inductive σʔλͷΈ શͯͷίϯετϥΫλʹ͍ͭͯఆٛ͞Ε͍ͯΔ͜ͱ ࠶ؼ͢Δ߹ύλʔϯϚονͰऔΓग़ͨ͠σʔλʹ͍ͭͯࣗΛݺ ΜͰ͍Δ͜ͱ Ҏ্ͷΑ͏ͳ੍ݶΛकΔ͜ͱͰɺʹґͬͯະఆٛ͋Δ͍ݕ͕ࠪࢭ· Βͳ͘ͳΔΑ͏ͳ (͓͔͠ͳ) ༷Λආ͚Δ͜ͱ͕Ͱ͖Δɻ 2ͦΕͧΕ VeriFast ͕ݕࠪ͢Δ 2017/04/29 VeriFast Termination Checking 21 / 42 -
࣍ VeriFast ֓આ ఀࢭੑݕࠪͱԿ͔ ఀࢭੑݕࠪ͜ͱ͡Ί Ұൠͷ߹ͷఀࢭੑݕࠪ ύλʔϯผఀࢭੑݕূ ࢀর fixpoint ͷ੍ݶ
fixpoint ʹΑΔؔͷఆٛʹɺҙͷ͕ؔهड़Ͱ͖ΔΘ͚Ͱͳ͘ز ੍͔͕ͭ͏ 2ɻ fixpoint ͷ੍ݶ ୯ಠͷ return ·ͨ switch จͰ͋Δ͜ͱ switch ʹͤΔͷ inductive σʔλͷΈ શͯͷίϯετϥΫλʹ͍ͭͯఆٛ͞Ε͍ͯΔ͜ͱ ࠶ؼ͢Δ߹ύλʔϯϚονͰऔΓग़ͨ͠σʔλʹ͍ͭͯࣗΛݺ ΜͰ͍Δ͜ͱ Ҏ্ͷΑ͏ͳ੍ݶΛकΔ͜ͱͰɺʹґͬͯະఆٛ͋Δ͍ݕ͕ࠪࢭ· Βͳ͘ͳΔΑ͏ͳ (͓͔͠ͳ) ༷Λආ͚Δ͜ͱ͕Ͱ͖Δɻ ⇒fixpoint ؔඞͣఀࢭ͢Δ 2ͦΕͧΕ VeriFast ͕ݕࠪ͢Δ 2017/04/29 VeriFast Termination Checking 21 / 42 -
࣍ VeriFast ֓આ ఀࢭੑݕࠪͱԿ͔ ఀࢭੑݕࠪ͜ͱ͡Ί Ұൠͷ߹ͷఀࢭੑݕࠪ ύλʔϯผఀࢭੑݕূ ࢀর fixpoint Ͱ͏·͍͘͘ཧ༝
fixpoint ͕ఀࢭ͢Δॏཁͳཧ༝ɺ inductive σʔλ্ͷ࠶ؼͰ͋Δ ࠶ؼݺͼग़͠ຖʹίϯετϥΫλ͕Ұͭͣͭണ͕Ε͍ͯ͘ 3 3Inductive σʔλͱ͍͏ͷɺجఈͷσʔλʹίϯετϥΫλΛ༗ݶճద༻ͯ͠ಘΒΕΔ σʔλͷ͜ͱ 2017/04/29 VeriFast Termination Checking 22 / 42 -
࣍ VeriFast ֓આ ఀࢭੑݕࠪͱԿ͔ ఀࢭੑݕࠪ͜ͱ͡Ί Ұൠͷ߹ͷఀࢭੑݕࠪ ύλʔϯผఀࢭੑݕূ ࢀর C ݴޠͰ͏·͍͔͘ͳ͍ཧ༝
C ݴޠͰఀࢭੑݕূ؆୯Ͱͳ͍ɻ C ݴޠͰѻ͏σʔλ inductive ͱݶΒͳ͍ ͔Γ͘͢σʔλߏ͕খ͘͞ͳΒͳ͍ 2017/04/29 VeriFast Termination Checking 23 / 42 -
࣍ VeriFast ֓આ ఀࢭੑݕࠪͱԿ͔ ఀࢭੑݕࠪ͜ͱ͡Ί Ұൠͷ߹ͷఀࢭੑݕࠪ ύλʔϯผఀࢭੑݕূ ࢀর inductive σʔλΛҰൠԽ
C ݴޠͰఀࢭੑΛݕࠪ͢Δʹ Inductive σʔλΛҰൠԽ͢Δඞཁ͕͋Δɻ ؔΛݺͼग़࣌͢ʹԿ͔͕ݮগ͢Δ ༗ݶεςοϓͰ࠷খʹͳΕΑ͍ 2017/04/29 VeriFast Termination Checking 24 / 42 -
࣍ VeriFast ֓આ ఀࢭੑݕࠪͱԿ͔ ఀࢭੑݕࠪ͜ͱ͡Ί Ұൠͷ߹ͷఀࢭੑݕࠪ ύλʔϯผఀࢭੑݕূ ࢀর Կ͔͕ݮΕΑ͍ Կ͕ݮΕ͍͍ͩΖ͏ʁ
2017/04/29 VeriFast Termination Checking 25 / 42 -
࣍ VeriFast ֓આ ఀࢭੑݕࠪͱԿ͔ ఀࢭੑݕࠪ͜ͱ͡Ί Ұൠͷ߹ͷఀࢭੑݕࠪ ύλʔϯผఀࢭੑݕূ ࢀর Կ͔͕ݮΕΑ͍ Կ͕ݮΕ͍͍ͩΖ͏ʁ
͑ɿcall-permission 2017/04/29 VeriFast Termination Checking 25 / 42 -
࣍ VeriFast ֓આ ఀࢭੑݕࠪͱԿ͔ ఀࢭੑݕࠪ͜ͱ͡Ί Ұൠͷ߹ͷఀࢭੑݕࠪ ύλʔϯผఀࢭੑݕূ ࢀর call permission
ؔݺͼग़͠ʹඞͣ call permission ͱ͍͏ݖར͕ඞཁͱ͍͏͜ͱʹ ͢Δɻ ؔ f ΛݺͿͨΊʹ call_perm(f) ͕ (Ұͭ) ඞཁ ࠷ॳʹؔͦΕͧΕͷ༗ݶݸͷ call_perm ͷετοΫΛ༩͑Δ ݕূग़དྷΕ༗ݶճ͔ؔ͠ݺͼग़͠ແ͍ͣͰ͋Δ 2017/04/29 VeriFast Termination Checking 26 / 42 -
࣍ VeriFast ֓આ ఀࢭੑݕࠪͱԿ͔ ఀࢭੑݕࠪ͜ͱ͡Ί Ұൠͷ߹ͷఀࢭੑݕࠪ ύλʔϯผఀࢭੑݕূ ࢀর call permission
ͷ࣮ VeriFast ͷඪ४ϥΠϒϥϦͰΈࠐΈͷड़ޠͱͯ͠ఏڙ͞ΕΔɻ call permission ͷ࣮ // prelude.h predicate call_perm_(void *f;); // VeriFast ͷ߹Ͱ͜͏͍͏Ϟϊ͋Δ (ৄࡉׂѪ) predicate call_below_perm_ (void *f;); 2017/04/29 VeriFast Termination Checking 27 / 42 -
࣍ VeriFast ֓આ ఀࢭੑݕࠪͱԿ͔ ఀࢭੑݕࠪ͜ͱ͡Ί Ұൠͷ߹ͷఀࢭੑݕࠪ ύλʔϯผఀࢭੑݕূ ࢀর call_perm ΛͲ͏ͬͯ༩͑Δ͔
࠷ॳʹؔͦΕͧΕͷ༗ݶݸͷ call_perm ͷετοΫΛ༩͑Δ ݕূ͠Α͏ͱ͍ͯ͠Δ͕ؔͲͷؔΛԿݺͿ͔ͳΜ͔ͯΒͳ͍. . . 2017/04/29 VeriFast Termination Checking 28 / 42 -
࣍ VeriFast ֓આ ఀࢭੑݕࠪͱԿ͔ ఀࢭੑݕࠪ͜ͱ͡Ί Ұൠͷ߹ͷఀࢭੑݕࠪ ύλʔϯผఀࢭੑݕূ ࢀর call_perm ΛͲ͏ͬͯ༩͑Δ͔
࠷ॳʹؔͦΕͧΕͷ༗ݶݸͷ call_perm ͷετοΫΛ༩͑Δ ݕূ͠Α͏ͱ͍ͯ͠Δ͕ؔͲͷؔΛԿݺͿ͔ͳΜ͔ͯΒͳ͍. . . ⇒ ଟॏू߹ (multiset,bag) Λ͏ 2017/04/29 VeriFast Termination Checking 28 / 42 -
࣍ VeriFast ֓આ ఀࢭੑݕࠪͱԿ͔ ఀࢭੑݕࠪ͜ͱ͡Ί Ұൠͷ߹ͷఀࢭੑݕࠪ ύλʔϯผఀࢭੑݕূ ࢀর ଟॏू߹ ଟॏू߹ɺཁૉͷॏෳΛڐ͢ू߹ɻ
{[1, 2, 3]} ⊎ {[2, 3, 4]} = {[1, 2, 2, 3, 3, 4]} 2017/04/29 VeriFast Termination Checking 29 / 42 -
࣍ VeriFast ֓આ ఀࢭੑݕࠪͱԿ͔ ఀࢭੑݕࠪ͜ͱ͡Ί Ұൠͷ߹ͷఀࢭੑݕࠪ ύλʔϯผఀࢭੑݕূ ࢀর ଟॏू߹ͷॱং ଟॏू߹ʹҎԼͷΑ͏ͳదͳॱংؔΛ༩͑Δɻ
In order to descend down the multiset order starting from a multiset M, one can replace any element of M with any number of lesser elements of X, any number of timesa. (খ͍͞ཁૉزͭ͋ͬͯΑΓେ͖͍ཁૉ 1 ͭΑΓখ͍͞) aจதͰݴٴ͕ແ͍͕ Dershowitz-Manna Ordering ͩͱࢥΘΕΔ ͜ͷنଇʹै͑ྫ͑ {[0, 0, 1, 2, 2, 2]} < {[0, 0, 0, 3]} ͕Γཱͭɻ 2017/04/29 VeriFast Termination Checking 30 / 42 -
࣍ VeriFast ֓આ ఀࢭੑݕࠪͱԿ͔ ఀࢭੑݕࠪ͜ͱ͡Ί Ұൠͷ߹ͷఀࢭੑݕࠪ ύλʔϯผఀࢭੑݕূ ࢀর ଟॏू߹ͷॱং ଟॏू߹ͷॱংؔΛ͏ͱҎԼͷ͜ͱ͕ݴ͑Δɻ
α′ < α =⇒ call_perm(α) ⊑ n · call_perm(α′) ͭ·Γɺ͋Δ call_perm ͔ΒɺΑΓখ͍ؔ͞ͷ call_perm زͭͰ (༗ ݶͷൣғͰ) ࡞Γग़ͤΔɻ 2017/04/29 VeriFast Termination Checking 31 / 42 -
࣍ VeriFast ֓આ ఀࢭੑݕࠪͱԿ͔ ఀࢭੑݕࠪ͜ͱ͡Ί Ұൠͷ߹ͷఀࢭੑݕࠪ ύλʔϯผఀࢭੑݕূ ࢀর ؔͷେখؔ ଟॏू߹ʹదͳॱংؔΛ࣋ͭΛ͢ඞཁ͕͋ͬͨɻ
call_perm ͷॱংؔͷఆٛʹؔͷॱংؔΛ͏ඞཁ͕͋Δɻ 2017/04/29 VeriFast Termination Checking 32 / 42 -
࣍ VeriFast ֓આ ఀࢭੑݕࠪͱԿ͔ ఀࢭੑݕࠪ͜ͱ͡Ί Ұൠͷ߹ͷఀࢭੑݕࠪ ύλʔϯผఀࢭੑݕূ ࢀর ؔͷେখؔ ଟॏू߹ʹదͳॱংؔΛ࣋ͭΛ͢ඞཁ͕͋ͬͨɻ
call_perm ͷॱংؔͷఆٛʹؔͷॱংؔΛ͏ඞཁ͕͋Δɻ ͦͦؔͷॱংؔ༩͑Δͷ͕େม. . . 2017/04/29 VeriFast Termination Checking 32 / 42 -
࣍ VeriFast ֓આ ఀࢭੑݕࠪͱԿ͔ ఀࢭੑݕࠪ͜ͱ͡Ί Ұൠͷ߹ͷఀࢭੑݕࠪ ύλʔϯผఀࢭੑݕূ ࢀর ؔͷେখؔ VeriFast
ʹҙͷؔϙΠϯλΛେখൺֱͰ͖Δ͕ؔ͋Δɻ ؔͷେখؔ // prelude.h fixpoint bool func_lt(void *f, void *g); /* VeriFast ΈࠐΈؔ */ 2017/04/29 VeriFast Termination Checking 33 / 42 -
࣍ VeriFast ֓આ ఀࢭੑݕࠪͱԿ͔ ఀࢭੑݕࠪ͜ͱ͡Ί Ұൠͷ߹ͷఀࢭੑݕࠪ ύλʔϯผఀࢭੑݕূ ࢀর ؔͷେখؔ ιʔείʔυ্ͷ্ԼؔΛͦͷ··͏ʂ
ؔͷେখؔ void foo (void) //@ requires emp; //@ ensures emp; { } void bar (void) //@ requires emp; //@ ensures emp; { } void cmp (void) //@ requires emp; //@ ensures emp; { //@ assert func_lt(foo , bar) == true; //@ assert func_lt(bar , foo) == false; } 2017/04/29 VeriFast Termination Checking 34 / 42 -
࣍ VeriFast ֓આ ఀࢭੑݕࠪͱԿ͔ ఀࢭੑݕࠪ͜ͱ͡Ί Ұൠͷ߹ͷఀࢭੑݕࠪ ύλʔϯผఀࢭੑݕূ ࢀর call_perm Λಋग़͢Δ
produce_call_below_perm_ͱ͍͏ΈࠐΈ໋ྩ 4 Λ͍ɺͦΕΛݺͼग़ͨ͠ ؔ f ʹ͍ͭͯ call_below_perm_(f) ͱ͍͏໋Λੜ͢Δɻ produce_call_below_perm void func (void) //@ requires emp; //@ ensures call_below_perm_ (func ); { //@ produce_call_below_perm_ (); //@ assert( call_below_perm_ (func )); } 4ΰʔετίϚϯυ (ghost command) ͱݺΕΔ 2017/04/29 VeriFast Termination Checking 35 / 42 -
࣍ VeriFast ֓આ ఀࢭੑݕࠪͱԿ͔ ఀࢭੑݕࠪ͜ͱ͡Ί Ұൠͷ߹ͷఀࢭੑݕࠪ ύλʔϯผఀࢭੑݕূ ࢀর ࣮ύλʔϯ ࢀরจ
[1] Ͱศٓతʹݕূ͢ΔϓϩάϥϜΛҎԼͷΑ͏ʹྨͯ͠આ໌ ͍ͯ͠Δɻ Upcalls Only ύλʔϯ Static Recursion ύλʔϯ Dynamic Binding ύλʔϯ 2017/04/29 VeriFast Termination Checking 36 / 42 -
࣍ VeriFast ֓આ ఀࢭੑݕࠪͱԿ͔ ఀࢭੑݕࠪ͜ͱ͡Ί Ұൠͷ߹ͷఀࢭੑݕࠪ ύλʔϯผఀࢭੑݕূ ࢀর Upcalls Only
ݺͼग़͞ΕΔ͕ؔɺશͯͦͷ࣌Ͱఆٛ͞Ε͓ͯΓɺ͔ͭ࠶ؼ͍ͯ͠ͳ ͍߹ɻ͜ͷ߹ callee ଆͷ call_perm ͷಋग़Λࢦఆ͢Δ͚ͩͰݕূͰ ͖Δ 5ɻ 5؆୯ͱݴ͍ͬͯͳ͍ 2017/04/29 VeriFast Termination Checking 37 / 42 -
࣍ VeriFast ֓આ ఀࢭੑݕࠪͱԿ͔ ఀࢭੑݕࠪ͜ͱ͡Ί Ұൠͷ߹ͷఀࢭੑݕࠪ ύλʔϯผఀࢭੑݕূ ࢀর Static Recursion
୯ҰϨΠϠͰ࠶ؼ͍ͯ͠Δ߹ɻ͜ͷ߹࠶ؼΛߏ͢ΔؔͦΕͧ ΕͰ࠷େͷ call_perm Λཁٻ͢Δɻ 2017/04/29 VeriFast Termination Checking 38 / 42 -
࣍ VeriFast ֓આ ఀࢭੑݕࠪͱԿ͔ ఀࢭੑݕࠪ͜ͱ͡Ί Ұൠͷ߹ͷఀࢭੑݕࠪ ύλʔϯผఀࢭੑݕূ ࢀর Dynamic Binding
நԽ͞ΕͨΠϯλʔϑΣʔεͷެ։͢ΔϝιουΛ༻͢Δ߹ɻC ݴ ޠͰؔϙΠϯλΛड͚औͬͯݺͼग़͢߹ʹ૬͢ΔɻJava ͷ߹ ͦͷ·· interface Λ͏߹ 6ɻ ͜ͷ߹Ҿͱ call_perm Λ߹Θͤͯ measure(ݮগ͢Δύϥϝʔλ) ͱ ͢Δɻ 6Ϋϥεͷෆม݅Λ͏ 2017/04/29 VeriFast Termination Checking 39 / 42 -
ࢀߟࢿྉ Bart Jacobs, Dragan Bosnacki, Ruurd Kuiper. Modular Termination Verification
ECOOP 2015 http://www.cs.kuleuven.be/~bartj/ecoop2015.pdf VeriFast official web site https://people.cs.kuleuven.be/~bart.jacobs/verifast/ VeriFast Tutorial(ຊޠ൛) https://github.com/jverifast-ug/translate/ -
Appendix ଟॏू߹ͷॱংؔ ଟॏू߹ʹಋೖͨ͠ॱংؔ Dershowitz–Manna ordering ͍͍ɺ͜Ε well-founded ordering Λ͢͜ͱ͕ΒΕ͍ͯΔɻ ⇒
ͭ·Γ࠷খʹ༗ݶεςοϓͰඞͣͨͲΓண͘ɻ 2017/04/29 VeriFast Termination Checking 41 / 42 -
Appendix Ԡ༻ ఀࢭੑݕࠪఀࢭ͢Δ͜ͱҎ֎ͷݕূʹԠ༻ग़དྷΔݟࠐΈ͕͋Δɻ ฒߦϓϩάϥϜ͕ఀࢭ͢Δͱ͍͏͜ͱ͔Β deadlock free Λূ໌͢Δ ఀࢭ͠ͳ͍͜ͱΛड़Δ͜ͱͰ liveness Λূ໌͢Δ
2017/04/29 VeriFast Termination Checking 42 / 42