Share
Embed
Modular Termination Verification on VeriFast
[静的コード解析の会#6](https://metasepi.connpass.com/event/67805/) で発表した資料です。
前回の発表(https://speakerdeck.com/eldesh/verifast-termination-checking-introduction-a) に続いて、
VeriFastによるC(およびJava)言語の停止性検査について説明しています。
停止性検査を行う背景、基本となる数学的な方針、VeriFastによる検査のアイディア、パターン毎の証明テクニックについて解説しています。
各分類パターンについては具体的なコード(片)に沿って解説しています。
参照:
Modular termination verification
Bart Jacobs, Dragan Bosnacki, and Ruurd Kuiper. At ECOOP 2015.
eldesh
January 25, 2018
Transcript
99 slides
-
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ Modular Termination Verification on VeriFast @eldesh https://twitter.com/eldesh http://d.hatena.ne.jp/eldesh ੩తίʔυղੳͷձ ୈ 6 ճ 2018/01/20 2018/01/20 VeriFast Termination Checking 1 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ ࣍ 1 VeriFast ֓ཁ 2 ఀࢭੑݕࠪͱԿ͔ 3 VeriFast ʹΑΔఀࢭੑݕࠪ 4 fixpoint ͷఀࢭੑ 5 C ݴޠؔͷఀࢭੑݕࠪ ଟॏू߹ͱ DW-Ordering 6 ύλʔϯผఀࢭੑݕূ Upcalls Only ύλʔϯ Static Recursion ύλʔϯ Dynamic Binding ύλʔϯ 7 ࢀর 2018/01/20 VeriFast Termination Checking 2 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ What is this slide? ͜ͷεϥΠυͰ VeriFast ʹΑΔ C ݴޠ͓Αͼ Java ϓϩάϥϜͷఀࢭੑݕ ূͷجૅͱͳΔ֓೦ɺ͓ΑͼͦΕΛ༻͍ͨݕূํɺ࣮ࡍͷॲཧܥͰͷѻ ͍ʹ͍ͭͯઆ໌͠·͢ɻ جૅͱͳΔ֓೦ ఀࢭੑূ໌ͷํ ࣮ࡍͷॲཧܥ্Ͱͷѻ͍ 2018/01/20 VeriFast Termination Checking 3 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ ఆ/ରௌऺ ඞਢ C ݴޠ͕͔Δ ·͍͠ ࣄલ/ࣄޙ݅ͷݕ͕ࠪͲΜͳͷͳͷ͔͔Δ 2018/01/20 VeriFast Termination Checking 4 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ VeriFast ͷೖతΛઆ໌͢Δ 2018/01/20 VeriFast Termination Checking 5 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ ఀࢭੑݕࠪͱ ϓϩάϥϜ͕ (༗ݶ࣌ؒʹ) ఀࢭ͢Δ͜ͱΛݕࠪ͢Δ͜ͱɻ 2018/01/20 VeriFast Termination Checking 6 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ VeriFast ͕ݕࠪ͢Δ͜ͱ ͱ͜ΖͰɺVeriFast ϓϩάϥϜ (ؔ) ͱɺͦͷࣄલ݅/ࣄޙ݅ͱͷҰ ؏ੑΛݕࠪ͢Δɻ 2018/01/20 VeriFast Termination Checking 7 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ VeriFast ͕ݕࠪ͢Δ͜ͱ ͱ͜ΖͰɺVeriFast ϓϩάϥϜ (ؔ) ͱɺͦͷࣄલ݅/ࣄޙ݅ͱͷҰ ؏ੑΛݕࠪ͢Δɻ ⇒ ͜ΕԿ͕ݕূग़དྷ͍ͯΔͷ͔ɻ 2018/01/20 VeriFast Termination Checking 7 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ VeriFast Ͱݕࠪͨؔ͠ ΤϯΩϡʔͷ༷ͷྫ void enqueue(struct queue *q, int x) //@ requires queue(q, ?vs); //@ ensures queue(q, iappend(vs , icons(x, inil ))); { ... } 2018/01/20 VeriFast Termination Checking 8 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ Hoare triple ؔͱɺͦͷࣄલ݅/ࣄޙ݅ 3 ͭΛ߹Θͤͯ Hoare triple ͱݺͿɻ ͜ΕΛܗࣜతʹѻ͏ࡍʹҎԼͷΑ͏ʹදه͢Δɻ Hoare triple ⊢ {P} c {Q} 2018/01/20 VeriFast Termination Checking 9 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ 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 ൃࢄͨ͠ঢ়ଶ (ແݶϧʔϓ) Λද͢ɻ 2018/01/20 VeriFast Termination Checking 10 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ Hoare triple ͷҙຯ Divergence |= Q ͱ͍͏͜ͱɺແݶϧʔϓʹͳͬͨ߹ৗʹ Q ࣄޙ ͕݅Γཱͭͱݴ͍ͬͯΔɻ 2018/01/20 VeriFast Termination Checking 11 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ Hoare triple ͷҙຯ Divergence |= Q ͱ͍͏͜ͱɺແݶϧʔϓʹͳͬͨ߹ৗʹ Q ࣄޙ ͕݅Γཱͭͱݴ͍ͬͯΔɻ ⇒VerifFast ແݶϧʔϓʹͳΔ͔Ͳ͏͔ݕূ͠ͳ͍ 2018/01/20 VeriFast Termination Checking 11 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ Hoare triple ͷҙຯ VeriFast ෦ਖ਼ੑ (partial correctness) Λ࣋ͭɻ ෦ਖ਼ੑ ϓϩάϥϜͷ࣮ߦ݁Ռ͕ग़ͨ (=ਖ਼͘͠ऴྃͨ͠) ߹ʹ ͦͷਖ਼͠͞Λอূ͢Δ ⇕ Partial Correctness ͜Εʹରͯ͠ɺৗʹϓϩάϥϜ͕ਖ਼͍݁͠ՌΛग़ྗ͢Δ߹ɺ͜ΕΛશ ਖ਼ੑ (Total Correctness) Λ࣋ͭ ͱ͍͏ɻ 2018/01/20 VeriFast Termination Checking 12 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ ఀࢭੑݕࠪͱ (࠶) ࠶ ϓϩάϥϜ͕ (༗ݶ࣌ؒʹ) ఀࢭ͢Δ͜ͱΛݕࠪ͢Δ͜ͱɻ ͱ͍͏͜ͱ. . . (෦ਖ਼ੑʹՃ͑ͯ) ఀࢭੑΛݕূ͢Δ ⇕ VeriFast ʹશਖ਼ੑΛ༩͑Δ ⇕ ϓϩάϥϜ͕ৗʹਖ਼͍͑͠Λฦ͢͜ͱΛอূͰ͖Δ 2018/01/20 VeriFast Termination Checking 13 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ ఀࢭੑݕࠪͷࢦఆ ؔͷఀࢭੑΛݕࠪ͢Δʹ௨ৗͷࣄલ, ࣄޙ݅ͷଞʹ terminates Λࢦ ఆ͢Δ. Կ͠ͳ͍ؔͷݕূ void empty_cmd (void) //@ requires emp; //@ ensures emp; //@ terminates; { } 2018/01/20 VeriFast Termination Checking 14 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ ࣗ໌ʹఀࢭ͢Δྫ 1 ϓϦϛςΟϒͳԋࢉࣗ໌ʹఀࢭ͢Δɻ less than ͷ༷ bool compare (int x, int y) //@ requires emp; //@ ensures result == (x < y); //@ terminates; { return x < y; // ฦΓେখൺֱͷ݁ՌʹҰக͢Δ } 2018/01/20 VeriFast Termination Checking 15 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ ࣗ໌ʹఀࢭ͢Δྫ 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; } } 2018/01/20 VeriFast Termination Checking 16 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ ࣗ໌ʹఀࢭ͢Δྫ 3 ఀࢭ͢ΔؔΛݺͿ͕ؔɺͦͷؔΑΓϑΝΠϧதͰԼͰఆٛ͞Ε͍ͯ Δ߹ఀࢭ͢Δ͜ͱ͕ࣗಈͰݕࠪͰ͖Δɻ call function int callee (int x) //@ requires emp; //@ ensures emp; //@ terminates; { return 0; } void caller (void) //@ requires emp; //@ ensures emp; //@ terminates; { callee (3); } 2018/01/20 VeriFast Termination Checking 17 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ ϧʔϓ ݕূʹৗʹඞཁͱͳΔϧʔϓΠϯόϦΞϯτʹՃ͑ͯɺdecreases ໋ྩͰݮ গ͢ΔύϥϝʔλΛࢦఆ͢Δ͜ͱͰఀࢭੑΛݕࠪ͢Δ͜ͱ͕Ͱ͖Δɻ 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; } } 2018/01/20 VeriFast Termination Checking 18 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ ࣗ໌Ͱͳ͍ఀࢭ͢Δྫ ΞοΧʔϚϯؔ 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 ߦ͋Δɻ 2018/01/20 VeriFast Termination Checking 19 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ جຊతͳൃ શͯͷݺͼग़͠γʔέϯε͕༗ݶεςοϓ͔͠ͳ͍͜ͱΛࣔͤྑ͍ɻ ⇒ Ͳ͏͢Δ͔ 2018/01/20 VeriFast Termination Checking 20 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ 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); } } 2018/01/20 VeriFast Termination Checking 21 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ fixpoint fixpoint ඞͣఀࢭ͢Δɻ fixpoint ؔͷྫ fixpoint int length <t>(list <t> xs) { switch (xs) { case nil: return 0; case cons(x, xs0): return 1 + length(xs0); } } 2018/01/20 VeriFast Termination Checking 21 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ fixpoint fixpoint ͳͥඞͣఀࢭ͢Δͷ͔ fixpoint ؔͷྫ fixpoint int length <t>(list <t> xs) { switch (xs) { case nil: return 0; case cons(x, xs0): return 1 + length(xs0); } } 2018/01/20 VeriFast Termination Checking 21 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ fixpoint ͷ੍ݶ fixpoint ʹΑΔؔͷఆٛʹɺҙͷ͕ؔهड़Ͱ͖ΔΘ͚Ͱͳ͘ز ੍͔͕ͭ͏ 1ɻ fixpoint ͷ੍ݶ ୯ಠͷ return ·ͨ switch จͰ͋Δ͜ͱ switch ʹͤΔͷ inductive σʔλͷΈ શͯͷίϯετϥΫλʹ͍ͭͯఆٛ͞Ε͍ͯΔ͜ͱ ࠶ؼ͢Δ߹ύλʔϯϚονͰऔΓग़ͨ͠σʔλʹ͍ͭͯࣗΛݺ ΜͰ͍Δ͜ͱ Ҏ্ͷΑ͏ͳ੍ݶΛकΔ͜ͱͰɺʹґͬͯະఆٛ͋Δ͍ݕ͕ࠪࢭ· Βͳ͘ͳΔΑ͏ͳ (͓͔͠ͳ) ༷Λආ͚Δ͜ͱ͕Ͱ͖Δɻ 1ͦΕͧΕ VeriFast ͕ݕࠪ͢Δ 2018/01/20 VeriFast Termination Checking 22 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ fixpoint ͷ੍ݶ fixpoint ʹΑΔؔͷఆٛʹɺҙͷ͕ؔهड़Ͱ͖ΔΘ͚Ͱͳ͘ز ੍͔͕ͭ͏ 1ɻ fixpoint ͷ੍ݶ ୯ಠͷ return ·ͨ switch จͰ͋Δ͜ͱ switch ʹͤΔͷ inductive σʔλͷΈ શͯͷίϯετϥΫλʹ͍ͭͯఆٛ͞Ε͍ͯΔ͜ͱ ࠶ؼ͢Δ߹ύλʔϯϚονͰऔΓग़ͨ͠σʔλʹ͍ͭͯࣗΛݺ ΜͰ͍Δ͜ͱ Ҏ্ͷΑ͏ͳ੍ݶΛकΔ͜ͱͰɺʹґͬͯະఆٛ͋Δ͍ݕ͕ࠪࢭ· Βͳ͘ͳΔΑ͏ͳ (͓͔͠ͳ) ༷Λආ͚Δ͜ͱ͕Ͱ͖Δɻ ⇒fixpoint ؔඞͣఀࢭ͢Δ 1ͦΕͧΕ VeriFast ͕ݕࠪ͢Δ 2018/01/20 VeriFast Termination Checking 22 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ fixpoint Ͱ͏·͍͘͘ཧ༝ fixpoint ͕ఀࢭ͢Δॏཁͳཧ༝ɺ inductive σʔλ্ͷ࠶ؼͰ͋Δ ࠶ؼݺͼग़͠ຖʹίϯετϥΫλ͕Ұͭͣͭണ͕Ε͍ͯ͘ 2 2Inductive σʔλͱ͍͏ͷɺجఈͷσʔλʹίϯετϥΫλΛ༗ݶճద༻ͯ͠ಘΒΕΔ σʔλͷ͜ͱ 2018/01/20 VeriFast Termination Checking 23 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ inductive ΑΓෳࡶͳͷ fixpoint inductive σʔλ্ͷؔͩͬͨɻͰ C ݴޠͰѻ͏σʔλߏ ͰͲ͏ͩΖ͏ʁ 2018/01/20 VeriFast Termination Checking 24 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ inductive ΑΓෳࡶͳͷ ॥͢Δσʔλߏ typedef struct C { int x; struct C * t; } C; void consumer (C * c) { ... consumer(c->t); } void producer (void) { C * ones = malloc(sizeof(C)); ones ->x = 1; ones ->t = ones; consumer(ones ); } 2018/01/20 VeriFast Termination Checking 25 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ inductive ΑΓෳࡶͳͷ ྫ͑॥͢Δσʔλߏ্ͷؔͷ߹ɺ༩͑ΒΕͨσʔλͷҰ෦ʹͭ ͍ͯ࠶ؼݺͼग़͠ 3 ͍͕ͯͯؔ͠ఀࢭ͢Δͱݴ͑ͳ͍ɻ ॥͢Δσʔλߏ void consumer (C * c) { ... consumer(c->t); } void producer (void) { C * ones = malloc(sizeof(C)); ones ->x = 1; ones ->t = ones; consumer(ones ); } 3fixpoint Ͱݕࠪ͢Δ༰ʹ૬͢Δ݅ 2018/01/20 VeriFast Termination Checking 26 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ C ݴޠͰ͏·͍͔͘ͳ͍ཧ༝ C ݴޠͰఀࢭੑݕূ؆୯Ͱͳ͍ɻ C ݴޠͰѻ͏σʔλ inductive ͱݶΒͳ͍ ͔Γ͘͢σʔλߏ͕খ͘͞ͳΒͳ͍ ॥σʔλߏ ڞ༗͞ΕͨมߋՄೳͳߏ 2018/01/20 VeriFast Termination Checking 27 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ C ݴޠͰ͏·͍͔͘ͳ͍ཧ༝ C ݴޠͰఀࢭੑݕূ؆୯Ͱͳ͍ɻ C ݴޠͰѻ͏σʔλ inductive ͱݶΒͳ͍ ͔Γ͘͢σʔλߏ͕খ͘͞ͳΒͳ͍ ॥σʔλߏ ڞ༗͞ΕͨมߋՄೳͳߏ inductive ͳσʔλΑΓҰൠతͳσʔλΛѻ͍͍ͨ 2018/01/20 VeriFast Termination Checking 27 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ ૅؔ inductive σʔλ (ͷίϯετϥΫλͷେখؔ) ͷҰൠԽͱͯ͠ૅؔ Λߟ͑Δɻ ͋Δू߹্ͷೋ߲ؔ R ͕ૅؔ Well-Founded Relation Ͱ͋Δͱ ૅؔ ∀S ⊆ X, S ̸= ∅ → ∃m ∈ S, ∀s ∈ S, (s, m) / ∈ R ૅؔ ू߹ X ্ͷೋ߲ؔ R ͕ɺۭͰͳ͍ू߹ S ⊂ X ͕ R ʹؔͯ͠ۃখݩΛ ࣋ͭ 2018/01/20 VeriFast Termination Checking 28 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ inductive σʔλ্ͷૅؔ fixpoint ؔͷఀࢭੑɺҾͷίϯετϥΫλͷ͕ؔݺͼग़͠ͷ ʹݮ͍ͬͯ͘͜ͱʹґ͍ͬͯͨɻ fixpoint ͷఀࢭੑ ࣗવ (ίϯετϥΫλͷ) ্ͷେখ͕ؔૅؔͰ͋Δ͜ͱʹґͬͯ ͍Δɻ ૅؔͷఆٛʹͯΊͯ֬ೝ͢Δɿ ૅؔ ∀S ⊆ X, S ̸= ∅ → ∃m ∈ S, ∀s ∈ S, (s, m) / ∈ R ࣗવ্ͷେখؔ ∀S ⊆ N, S ̸= ∅ → ∃m ∈ S, ∀s ∈ S, (s, m) / ∈ (<) 2018/01/20 VeriFast Termination Checking 29 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ ૅؔͷ؍ ΑΓײతʹɺૅؔͱɺू߹্ͷೋ߲ؔ R ͕ແݶ߱Լྻ 4 Λ࣋ ͨͳ͍͜ͱΛݴ͏ɻ ͜Εܭࢉ͕ਐΉʹ࿈ΕͯԿ͔͕ૅؔͰ͋ΔେখؔʹԊͬͯݮগ͠ ͍ͯ͘ͳΒɺͦͷܭࢉ͕༗ݶ࣌ؒͰఀࢭ͢Δ͜ͱʹରԠ͢Δɻ(ؾ͕͢Δ) 4ৗʹΑΓখ͍͞ݩ͕ଘࡏ͢Δ͜ͱ 2018/01/20 VeriFast Termination Checking 30 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ ݮগ͢ΔϞϊ ૅؔΛಋೖͯ͠ inductive σʔλ (্ͷେখؔ) ΑΓॊೈͳೋ߲ؔ ͕ѻ͑ΔΑ͏ʹͳͬͨɻͰ C ݴޠͰԿ͕ݮ͍ͬͯΔͱߟ͑Ε͍͍ͩ Ζ͏ʁ 2018/01/20 VeriFast Termination Checking 31 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ ݮগ͢ΔϞϊ ૅؔΛಋೖͯ͠ inductive σʔλ (্ͷେখؔ) ΑΓॊೈͳೋ߲ؔ ͕ѻ͑ΔΑ͏ʹͳͬͨɻͰ C ݴޠͰԿ͕ݮ͍ͬͯΔͱߟ͑Ε͍͍ͩ Ζ͏ʁ ఏҊɿcall permission (ؔΛݺͿݖར)a aʮpermissionʯͳͷͰʮڐʯͷํ͕ద͔ 2018/01/20 VeriFast Termination Checking 31 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ call permission ͷಋೖ ؔݺͼग़͠ʹඞͣ call permission ͱ͍͏ݖར͕ඞཁͱ͍͏͜ͱʹ ͢Δɻ ؔ f ΛݺͿͨΊʹ call_perm(f) ͕ (Ұͭ) ඞཁ ؔ f ΛݺͿʹ call_perm(f) ͕ (Ұͭ) ݮগ 2018/01/20 VeriFast Termination Checking 32 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ call permission ͷಋೖ ؔݺͼग़͠ʹඞͣ call permission ͱ͍͏ݖར͕ඞཁͱ͍͏͜ͱʹ ͢Δɻ ؔ f ΛݺͿͨΊʹ call_perm(f) ͕ (Ұͭ) ඞཁ ؔ f ΛݺͿʹ call_perm(f) ͕ (Ұͭ) ݮগ ࠷ॳʹؔͦΕͧΕͷ༗ݶݸͷ call_perm ͷετοΫΛ༩͑Δ ͔ؔΒݺͼग़͢શͯͷؔͷ call_perm Λࣄલ݅ʹཁٻ͢Δ ݕূΛύεग़དྷΕ༗ݶճ͔ؔ͠ݺͼग़͠ແ͍ (ఀࢭ͢Δ) ͣͰ ͋Δ 2018/01/20 VeriFast Termination Checking 32 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ call permission ͷ࣮ call permission ͷطଘͷ predicate ͱಉ༷ͷΈͰՄೳɻ ඪ४ϥΠϒϥϦͰҙͷؔϙΠϯλ্ͷΈࠐΈͷ predicate ͱͯ͠ఏ ڙ͞Εɺ࣮ମϢʔβଆʹެ։͞Ε͍ͯͳ͍ɻ call permission ͷ࣮ // prelude.h predicate call_perm_(void *f;); ;(ηϛίϩϯ) ͕͍͍ͯΔͷͰɺಉ͡ϙΠϯλʹ͍ͭͯͷ call_perm_Ұ ҙʹఆ·Δɻ 2018/01/20 VeriFast Termination Checking 33 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ call_perm_ͷ༻ ؔ f ΛݺͿͨΊʹ call_perm_(f) ͕ඞཁͱ͞ΕΔ call_perm_ͷ༻ (pseudo) void call (void) //@ requires call_perm_(f); //@ ensures emp; //@ terminates; { f(); } 2018/01/20 VeriFast Termination Checking 34 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ call_perm_ͷ༻ ؔ f Λ 2 ճݺͿ͜ͱͰ͖ͳ͍ɻ call_perm_ͷ༻ (pseudo) void call (void) //@ requires call_perm_(f); //@ ensures emp; //@ terminates; { f(); f(); // ~should_fail } 2018/01/20 VeriFast Termination Checking 35 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ call_perm_ͷ༻ ؔ f Λ 2 ճݺͿͨΊʹ call_perm_(f) ͕ 2 ͭඞཁ call_perm_ͷ༻ void call (void) //@ requires [2] call_perm_(f); //@ ensures emp; //@ terminates; { f(); f(); } 2018/01/20 VeriFast Termination Checking 35 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ call_perm_ͷߏ ؔΛݺͿͨΊʹ call_perm_͕ඞཁ͕ͩɺcall_perm_ͱ͍͏໋ͷΠϯ ελϯεߏͰ͖ͣɺ·ͣ call_below_perm_ͱ͍͏໋Λܦ༝͢Δ ඞཁ͕͋Δɻ call_below_perm // prelude.h predicate call_below_perm_ (void *f;); 2018/01/20 VeriFast Termination Checking 36 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ call_below_perm_ͷಋग़ call_below_perm_ΛಘΔʹɺproduce_call_below_perm_ͱ͍͏ΈࠐΈ໋ ྩ 5 Λ͏ɻ produce_call_below_perm void func (void) //@ requires emp; //@ ensures call_below_perm_ (func ); { //@ produce_call_below_perm_ (); //@ assert( call_below_perm_ (func )); } ͋Δؔ func ͔Β produce_call_below_perm_ΛݺͿͱɺ call_below_perm_(func) ͕ (Ұͭ) खʹೖΔɻ 5ΰʔετίϚϯυ (ghost command) ͱݺΕΔ 2018/01/20 VeriFast Termination Checking 37 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ call_perm_Λಋग़͢Δ call_below_perm_(f) ͔Βඪ४ϥΠϒϥϦͷఏڙ͞ΕΔิʹΑͬͯ call_perm_(g)(ͨͩ͠ g < f ) ͕ಋग़Ͱ͖Δɻ call_below_perm_͔Β call_perm_Λಋग़͢Δ void g (void ); //@ terminates; void f (void) //@ requires emp; //@ ensures emp; //@ terminates; { //@ produce_call_below_perm_ (); //@ call_below_perm__elim (f); //@ consume_call_perm_for (g); g(); } 2018/01/20 VeriFast Termination Checking 38 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ call_below_perm_ call_below_perm_ఀࢭੑݕࠪͷϞδϡϥϦςΟΛߴΊΔͨΊʹಋೖ͞Ε ໋ͨ 6 Ͱɺcall_perm_ͱͷؒʹҎԼͷΑ͏ͳؔͷେখؔ 7 ʹجͮ͘େ খ͕ؔఆٛ͞Ε͍ͯΔɻ call_perm_ͱ call_below_perm_ͷେখؔ ∀f g, g < f → call_perm_(g) < call_below_perm_(f ) < call_perm_(f ) 6චऀͷ༧ 7ؔͷେখؔޙड़ 2018/01/20 VeriFast Termination Checking 39 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ call_below_perm_ call_below_perm_ఀࢭੑݕࠪͷϞδϡϥϦςΟΛߴΊΔͨΊʹಋೖ͞Ε ໋ͨ 6 Ͱɺcall_perm_ͱͷؒʹҎԼͷΑ͏ͳؔͷେখؔ 7 ʹجͮ͘େ খ͕ؔఆٛ͞Ε͍ͯΔɻ call_perm_ͱ call_below_perm_ͷେখؔ ؔ f ͷఆٛதͰߏͰ͖Δ call_below_perm_(f) ɺcall_perm_(f) ະຬ Ͱ࠷େͷ call permssionɻ 6චऀͷ༧ 7ؔͷେখؔޙड़ 2018/01/20 VeriFast Termination Checking 39 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ ଟॏू߹ͱ DW-Ordering call_perm ΛͲ͏ͬͯ༩͑Δ͔ call_perm_ͱ call_below_perm_Λ͑ɺݕূ͢ΔରؔΑΓখ͍ؔ͞ Λܾ·ͬͨճݺͼग़͢έʔεʹ͍ͭͯݕূͰ͖ͦ͏ͩͬͨɻ 2018/01/20 VeriFast Termination Checking 40 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ ଟॏू߹ͱ DW-Ordering call_perm ΛͲ͏ͬͯ༩͑Δ͔ ؔͷఀࢭੑΛݕূ͢ΔʹҎԼͷखॱ͕ඞཁͩͬͨɻ ࠷ॳʹؔͦΕͧΕͷ༗ݶݸͷ call_perm ͷετοΫΛ༩͑Δ ͱ͜Ζ͕Ұൠʹɺݕূ͠Α͏ͱ͍ͯ͠Δ͕ؔͲͷؔΛԿݺͿ͔ͳΜ ͔ͯΒͳ͍. . . 2018/01/20 VeriFast Termination Checking 41 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ ଟॏू߹ͱ DW-Ordering call_perm ΛͲ͏ͬͯ༩͑Δ͔ ؔͷఀࢭੑΛݕূ͢ΔʹҎԼͷखॱ͕ඞཁͩͬͨɻ ࠷ॳʹؔͦΕͧΕͷ༗ݶݸͷ call_perm ͷετοΫΛ༩͑Δ ͱ͜Ζ͕Ұൠʹɺݕূ͠Α͏ͱ͍ͯ͠Δ͕ؔͲͷؔΛԿݺͿ͔ͳΜ ͔ͯΒͳ͍. . . ⇒ ଟॏू߹ (multiset,bag) ͱ DW-Ordering Λ͏ 2018/01/20 VeriFast Termination Checking 41 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ ଟॏू߹ͱ DW-Ordering ଟॏू߹ ଟॏू߹ (multi set) ɺཁૉͷॏෳΛڐ͢ू߹ɻ ଟॏू߹ͷྫ {[]} {[1, 2, 3]} {[1, 3, 3, 5, 5, 5, 6]} ͦΕͧΕͷཁૉΛଟॏͱݺͼɺҎԼͷΑ͏ʹදه͢Δɻ ଟॏ M = {[1, 3, 3, 5, 5, 5, 6]} ͷ࣌ɺ M(0) = 0 M(3) = 2 M(5) = 3 2018/01/20 VeriFast Termination Checking 42 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ ଟॏू߹ͱ DW-Ordering ଟॏू߹ ࠓճͷٞͰ݁߹ (join) ͱݺΕΔૢ࡞͕ඞཁʹͳΔ 8ɻ ଟॏू߹ͷ݁߹ (join) {[1, 2, 3]} ⊎ {[2, 3, 4]} = {[1, 2, 2, 3, 3, 4]} 8࣮୯ͳΔϦετͷ࿈݁ 2018/01/20 VeriFast Termination Checking 43 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ ଟॏू߹ͱ DW-Ordering ଟॏू߹্ͷॱংؔ ॱংؔͷ͋Δཁૉ͔ΒͳΔଟॏू߹ʹҎԼͷΑ͏ͳॱংؔΛ༩͑ Δ 9ɻ Dershowitz–Manna ordering ଟॏू߹ M,N ʹ͍ͭͯɺେখؔ (<) ΛҎԼͷΑ͏ʹఆٛ͢Δɻ M < N ≡ M ̸= N ∧ ∀y ∈ S, M(y) > N(y) → ∃x ∈ S, y < x ∧ M(x) < N(x) ͜ͷنଇʹै͑ྫ͑ {[0, 0, 1, 2, 2, 2]} < {[0, 0, 0, 3]} ͕Γཱͭɻ 9จதͰཅʹݴٴ͕ແ͍͕ Dershowitz-Manna Ordering ͩͱࢥΘΕΔ 2018/01/20 VeriFast Termination Checking 44 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ ଟॏू߹ͱ DW-Ordering ଟॏू߹্ͷॱংؔ ॱংؔͷ͋Δཁૉ͔ΒͳΔଟॏू߹ʹҎԼͷΑ͏ͳॱংؔΛ༩͑ Δ 9ɻ Dershowitz–Manna ordering[1] 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 times. (খ͍͞ཁૉزͭ͋ͬͯΑΓେ͖͍ཁૉ 1 ͭΑΓখ͍͞) ͜ͷنଇʹै͑ྫ͑ {[0, 0, 1, 2, 2, 2]} < {[0, 0, 0, 3]} ͕Γཱͭɻ 9จதͰཅʹݴٴ͕ແ͍͕ Dershowitz-Manna Ordering ͩͱࢥΘΕΔ 2018/01/20 VeriFast Termination Checking 44 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ ଟॏू߹ͱ DW-Ordering func_lt ͱ͜Ζ͕ VeriFast ʹҙͷؔϙΠϯλΛେখൺֱͰ͖Δ͕ؔ͋Δɻ ؔͷେখؔ // prelude.h fixpoint bool func_lt(void *f, void *g); 2018/01/20 VeriFast Termination Checking 45 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ ଟॏू߹ͱ DW-Ordering func_lt ͱ͜Ζ͕ VeriFast ʹҙͷؔϙΠϯλΛେখൺֱͰ͖Δ͕ؔ͋Δɻ ؔͷେখؔ // prelude.h fixpoint bool func_lt(void *f, void *g); ⇒ ͲͷΑ͏ʹେখؔΛఆٛ͢Δͷ͔ʁ 2018/01/20 VeriFast Termination Checking 45 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ ଟॏू߹ͱ DW-Ordering func_lt ιʔείʔυ্ͷ্ԼؔΛͦͷ··͏ʂ ؔͷେখؔ void foo (void) //@ terminates; { } void bar (void) //@ terminates; { } void cmp (void) //@ terminates; { //@ assert func_lt(foo , bar) == true; //@ assert func_lt(bar , foo) == false; } ͜ͷେখؔ VeriFast ͕ࣗಈͰಋग़ͯ͘͠ΕΔɻ 2018/01/20 VeriFast Termination Checking 46 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ ଟॏू߹ͱ DW-Ordering DW-Ordering Λಋग़ͨ͠खॱ ͜Ε·ͰͰҎԼͷखॱͰଟॏू߹্ͷૅ͕ؔखʹೖͬͨɻ ؔʹେখ͕ؔಋೖ͞Εͨ (func_lt ͕͑Δ) call_perm_্ʹͦͷେখؔΛͦͷ··͏ call_perm_্ͷେখ͔ؔΒ Dershowitz-Manna ordering ͰૅؔΛ ఆٛ͢Δ 2018/01/20 VeriFast Termination Checking 47 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ ଟॏू߹ͱ DW-Ordering DW-Ordering Λಋग़ͨ͠खॱ ͜Ε·ͰͰҎԼͷखॱͰଟॏू߹্ͷૅ͕ؔखʹೖͬͨɻ ͜ͷؔΛ͏ͱɺΑΓখ͍͞ call_perm_Λҙݸಋग़͢Δ͜ͱ͕ग़དྷΔɻ derive permissions void g (void) //@ requires call_perm ({h}); { func_t * ff = f; //@ call_perm_below (2); //@ assert [2] call_perm_(f); //@ consume_call_perm_for (f); //@ consume_call_perm_for (f); ff(); ff(); } void f (void) //@ : func_t { } void h (void) { } 2018/01/20 VeriFast Termination Checking 47 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ ଟॏू߹ͱ DW-Ordering C ݴޠؔͷఀࢭੑݕࠪ·ͱΊ call permission ͱ͍͏֓೦Λಋೖ call_perm_ͷଟॏू߹্ͰૅؔΛఆٛ͢Δ ఆٛͨ͠ૅؔʹΑͬͯɺΑΓখ͍͞ call_perm_ҙͷ͚ͩಋ ग़Ͱ͖Δ 2018/01/20 VeriFast Termination Checking 48 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ ଟॏू߹ͱ DW-Ordering C ݴޠؔͷఀࢭੑݕࠪ·ͱΊ call permission ͱ͍͏֓೦Λಋೖ call_perm_ͷଟॏू߹্ͰૅؔΛఆٛ͢Δ ఆٛͨ͠ૅؔʹΑͬͯɺΑΓখ͍͞ call_perm_ҙͷ͚ͩಋ ग़Ͱ͖Δ ݕࠪରʹؚ·ΕΔؔͷதͰɺ࠷େͷؔΛݺͿ͜ͱ͕ग़དྷΔ call_perm_Λ༩͑Εɺଞͦͷ call_perm_͔Βಋग़͢ΕΑ͍ ϓϩάϥϜશମΛݕূ͍ͨ͠߹ main ؔΛϑΝΠϧඌʹఆٛ ͠ɺcall_below_perm_(main) Λ͏ 2018/01/20 VeriFast Termination Checking 48 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ ύλʔϯผݕࠪํ๏ ͜͜·ͰͰ VeriFast ʹΑΔఀࢭੑݕࠪͷ͓͓ΑͦͷํͱཧతͳഎܠΛ આ໌͖ͯͨ͠ɻ͜ΕҎ߱Ͱݕূ͢ΔରίʔυͷύλʔϯຖʹɺऍΛ ͚͍ͯ͘ํ๏ͱ࣮ࡍͷίʔυΛղઆ͢Δɻ 2018/01/20 VeriFast Termination Checking 49 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ ύλʔϯͷྨ ղઆ͢ΔύλʔϯͷྨҎԼͷΑ͏ʹ໊લ͕͍͍ͯΔ 10 Upcalls Only ύλʔϯ Static Recursion ύλʔϯ Dynamic Binding ύλʔϯ 10Jacobs(2015)[1] ͰఏҊ͞Ε͍ͯΔͷͱಉҰɻ 2018/01/20 VeriFast Termination Checking 50 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ Upcalls Only ύλʔϯ Upcalls Only ݺͼग़͞ΕΔ͕ؔɺશͯͦͷ࣌Ͱఆٛ͞Ε͓ͯΓɺ͔ͭ࠶ؼ͍ͯ͠ͳ ͍ύλʔϯɻ ͜ͷ߹ؔݺͼग़͕͠ৗʹࣗΑΓখ͍ؔ͞ͷݺͼग़͠ʹͳΔͨΊɺ ࣗ໌ʹఀࢭ͢Δͱݴ͑Δɻ 2018/01/20 VeriFast Termination Checking 51 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ Upcalls Only ύλʔϯ Upcalls Only ͜ͷ߹ࣗಈͰݕࠪͰ͖Δɻ upcalls_only void foo(void) //@ requires emp; //@ ensures emp; //@ terminates; {} void bar(void) //@ requires emp; //@ ensures emp; //@ terminates; { foo (); } void bazz(void) //@ requires emp; //@ ensures emp; //@ terminates; { bar (); } ͜ͷ߹ɺcall_perm_ূ໌ίϯςΩετதʹ໌ࣔతʹݱΕͳ͍ɻ 2018/01/20 VeriFast Termination Checking 52 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ Static Recursion ύλʔϯ Static Recursion ୯ҰϨΠϠ 11 Ͱ૬ޓ࠶ؼ͍ͯ͠Δ߹ɺ͜ΕΛ static recursion ύλʔϯ ͱݺͿɻ࠶ؼ͍ͯ͠Δύλʔϯ͜Εʹؚ·ΕΔɻ 11ಉҰϑΝΠϧ 2018/01/20 VeriFast Termination Checking 53 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ Static Recursion ύλʔϯ Static Recursion యܕతͳྫͱͯ͠૬ޓ࠶ؼͨ͠ۮدఆͷؔΛѻ͏ɻ bool isOdd (int x) //@ requires 0 <= x; //@ ensures emp; //@ terminates; { if (x == 0) return false; return isEven(x -1); } bool isEven(int x) //@ requires 0 <= x; //@ ensures emp; //@ terminates; { if (x == 0) return true; return isOdd(x -1); } 2018/01/20 VeriFast Termination Checking 54 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ Static Recursion ύλʔϯ Static Recursion ࠶ؼؔͰɺfunc_lt ʹґΔେখ͕ؔٯస͢Δؔݺͼग़͠ 12 Λඞͣ ؚΉͨΊɺ୯ʹؔͷେখΛൺֱ͢Δ͚ͩͰݕࠪͰ͖ͳ͍ɻ bool isOdd (int x) //@ requires 0 <= x; //@ ensures emp; //@ terminates; { if (x == 0) return false; return isEven(x -1); } bool isEven(int x) //@ requires 0 <= x; //@ ensures emp; //@ terminates; { if (x == 0) return true; return isOdd(x -1); } 12ؔͷݺग़ଆ͕ݺΕΔଆͷؔΑΓখ͍͞ 2018/01/20 VeriFast Termination Checking 54 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ Static Recursion ύλʔϯ isEven/isOdd ͷݕূํ isEven, isOdd ͷఀࢭੑΛݕূ͢ΔʹɺͦΕͧΕͷҾ͕খ͘͞ͳ͍ͬͯ ͘ (༗ݶճͷݺͼग़͠Ͱ 0 ʹͳΔ) ͱ͍͏ใΛ͍͍ͨɻ͜ͷͨΊʹ predicate call_perm_level Λ͏ɻ 2018/01/20 VeriFast Termination Checking 55 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ Static Recursion ύλʔϯ call_perm_level call_perm_level call_perm_ͱɺૅؔΛ࣋ͭҙͷܕ͔Βಋग़͞Ε Δɺมܗͨ͠λϓϧɻ13 call_perms.gh predicate call_perm_level <t>( // t ্ͷେখؔͱ t ܕͷ pair <fixpoint(t, t, bool), t> level , // ؔϙΠϯλͷଟॏू߹ list <void *> fs; ); 13ؔؒͷେখؔॲཧܥఆٛͳͷͰෆཁ 2018/01/20 VeriFast Termination Checking 56 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ Static Recursion ύλʔϯ call_perm_level σεΫτϥΫτ͢Ε call_perm_͕ಘΒΕΔɻ call_perms.gh lemma void consume_call_perm_level_for <t>( void *f); requires call_perm_level <t>(? level , ?fs) &*& mem(f, fs) == true; ensures call_perm_(f); 2018/01/20 VeriFast Termination Checking 56 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ Static Recursion ύλʔϯ call_perm_level DW-Ordering ʹΑΓɺλϓϧͷୈ 1 ཁૉ͕ૅؔͰΑΓখ͍͞ΛऔΔ Α͏ͳҙݸͷ call_perm_level ʹஔ͖͑ͯΑ͍ɻσεΫτϥΫτͷ໋ ͱ߹ΘͤΔͱɺcall_perm_Λ૿͍ͤͯΔ͜ͱʹҙɻ call_perms.gh lemma void call_perm_level_weaken <t>( real frac0 , fixpoint(t, t, bool) lt , t level0 , list <void *> fs0 , real frac1 , t level1 ); requires [_]is_wf(lt) &*& lt(level1 , level0) == true &*& 1 <= frac0 &*& 1 <= frac1 &*& [frac0]call_perm_level <t>( pair(lt , level0), fs0); ensures [frac1]call_perm_level <t>( pair(lt , level1), fs0); 2018/01/20 VeriFast Termination Checking 56 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ Static Recursion ύλʔϯ isEven/isOdd ͷݕূํ ࠓճͷྫͷݕূͰ isOdd(খ͍ؔ͞) ͔Β isEven(େ͖͍ؔ) ΛݺͿ͜ ͱ͕ग़དྷͳ͍ͷ͕ͩͬͨɻ͜Εઌʹڍ͛ͨ call_perm_level Λ͏ ͱҎԼͷΑ͏ʹճආग़དྷΔɻ call_perm_level(pair(lt,x),{isEven}) ͔Β call_perm_level(pair(lt,x-1),{isEven}) Λಋग़͢Δ 2 ͭ͋Δ call_perm_level ͷҰ͔ͭΒ call_perm_(isEven) Λಋग़͢ Δ (ͱ isEven ΛݺͿ͜ͱ͕ग़དྷΔ) isOdd ͷࣄલ݅Ͱ call_perm_level(pair(lt,x),{isEven}) Λཁٻ ͢Δ 2018/01/20 VeriFast Termination Checking 57 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ Static Recursion ύλʔϯ isEven/isOdd ͷݕূํ ࠓճͷྫͷݕূͰ isOdd(খ͍ؔ͞) ͔Β isEven(େ͖͍ؔ) ΛݺͿ͜ ͱ͕ग़དྷͳ͍ͷ͕ͩͬͨɻ͜Εઌʹڍ͛ͨ call_perm_level Λ͏ ͱҎԼͷΑ͏ʹճආग़དྷΔɻ isOdd(ऍத) bool isOdd (int x) /*@ requires 0 <= x &*& call_perm_level (pair(lt , x), {isEven }); @*/ { if (0 == x) { return false; } else { //@ is_wf_lt (); //@ call_perm_level_weaken (1, lt , x, {isEven}, 2, x -1); //@ consume_call_perm_level_for (isEven ); return isEven(x -1); } } ͜ΕͰओཁͳ͕ย͍ͨɻ͋ͱ isOdd ͷࣄલ͕݅ຬͨͤΕΑ͍ɻ 2018/01/20 VeriFast Termination Checking 57 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ Static Recursion ύλʔϯ isEven ͷࣄલ݅ isOdd ͷࣄલ݅Ͱ call_perm_level(pair(lt,x),{isEven}) ͕ཁٻ͞Εͯ ͍Δ͕ɺ͜Ε isEven ͷ࣮தʹಋग़͢Δ͜ͱग़དྷͳ͍ 13ɻ 13ؔ f தͰɺΑΓখ͍͞ call_below_perm_(f) ͔͠ಋग़ग़དྷͳ͍ 2018/01/20 VeriFast Termination Checking 58 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ Static Recursion ύλʔϯ isEven ͷࣄલ݅ isOdd ͷࣄલ݅Ͱ call_perm_level(pair(lt,x),{isEven}) ͕ཁٻ͞Εͯ ͍Δ͕ɺ͜Ε isEven ͷ࣮தʹಋग़͢Δ͜ͱग़དྷͳ͍ 13ɻ ͳͷͰɺ isEven Ͱࣄલ݅ʹಉ͡ͷΛཁٻ͢Δɻ 13ؔ f தͰɺΑΓখ͍͞ call_below_perm_(f) ͔͠ಋग़ग़དྷͳ͍ 2018/01/20 VeriFast Termination Checking 58 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ Static Recursion ύλʔϯ isEven ͷࣄલ݅ isOdd ͷࣄલ݅Ͱ call_perm_level(pair(lt,x),{isEven}) ͕ཁٻ͞Εͯ ͍Δ͕ɺ͜Ε isEven ͷ࣮தʹಋग़͢Δ͜ͱग़དྷͳ͍ 13ɻ isEven(ऍத) bool isEven(int x) /*@ requires 0 <= x &*& call_perm_level (pair(lt , x), {isEven }); @*/ { if (0 == x) { return true; } else { //@ is_wf_lt (); //@ call_perm_level_weaken (1, lt , x, {isEven}, 1, x - 1); return isOdd(x -1); } } isOdd ͱҟͳΓΑΓখ͍ؔ͞Λݺͼग़ͨ͢Ίɺcall_perm_level Λ૿͢ ඞཁͳ͍ɻ 13ؔ f தͰɺΑΓখ͍͞ call_below_perm_(f) ͔͠ಋग़ग़དྷͳ͍ 2018/01/20 VeriFast Termination Checking 58 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ Static Recursion ύλʔϯ isEven/isOdd ͷϥούʔ ͜ΕͰ isEven ͱ isOdd ͷఀࢭੑ͕ݕࠪͰ͖͕ͨɺͦΕͧΕͷࣄલ݅ʹ͜ Ε·Ͱඞཁͳ͔ͬͨ call_perm_level Λཁٻ͢ΔΑ͏ͳͬͯ͠·ͬͨɻ ͜Ε isEven ΑΓେ͖͍ؔͱͯ͠ϥούʔΛఆٛ͢Ε؆୯ʹղܾ ͢Δɻ 2018/01/20 VeriFast Termination Checking 59 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ Static Recursion ύλʔϯ isEven/isOdd ͷϥούʔ bool isOdd (int x) /*@ requires 0 <= x &*& call_perm_level (pair(lt , x), {isEven }); @*/ { ... } bool isEven(int x) { ... } bool isOddWrapper (int x) //@ requires 0 <= x; { //@ produce_call_below_perm_ (); //@ call_below_perm__elim (isOddWrapper ); //@ call_perm_level (1, pair(lt , x), {isEven }); return isOdd(x); } bool isEvenWrapper (int x) { ... ͱಉ༷isOddWrapper } 2018/01/20 VeriFast Termination Checking 59 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ Static Recursion ύλʔϯ isEven/isOdd ͷϥούʔ ϥούʔͷࣄલ݅ͱͯ͠ call_perm_level ͕ݱΕ͍ͯͳ͍͜ͱʹɻ ϥούʔΛϔομ͔Βެ։͢ΕɺϢʔβʹͱͬͯఀࢭੑݕࠪͷͨΊʹ ࣄલ͕݅ෳࡶʹΒͣʹࡁΉɻ bool isOddWrapper (int x) //@ requires 0 <= x; { //@ produce_call_below_perm_ (); //@ call_below_perm__elim (isOddWrapper ); //@ call_perm_level (1, pair(lt , x), {isEven }); return isOdd(x); } bool isEvenWrapper (int x) { ... ͱಉ༷isOddWrapper } 2018/01/20 VeriFast Termination Checking 59 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ Static Recursion ύλʔϯ VeriFast ͷ੍ݶ ݱঢ়ͷ VeriFast Ͱ࣮ͷ੍ݶͰ isOdd ͔Β isEven ͷݺग़͠ग़དྷͳ ͍ɻ͜ΕؔϙΠϯλΛܦ༝ͨ͠ݺͼग़͠ʹ͢Εճආग़དྷΔɻ typedef bool is_even_fn(int x); /*@ requires 0 <= x &*& call_perm_level (pair(lt , x), {isEven }); @*/ bool isOdd (int x) /*@ requires 0 <= x &*& call_perm_level (pair(lt , x), {isEven }); @*/ { if (0 == x) { return false; } else { is_even_fn * evenp = isEven; //@ is_wf_lt (); //@ call_perm_level_weaken (1, lt , x, {isEven}, 2, x -1); //@ consume_call_perm_level_for (isEven ); return evenp(x -1); } } 2018/01/20 VeriFast Termination Checking 60 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ Static Recursion ύλʔϯ Static Recursion ͷݕূखॱ ͜Ε·ͰͷखॱΛ·ͱΊΔɻ ࣗҎ্ͷؔͷݺͼग़͠ΛؔϙΠϯλܦ༝ʹ͢Δ (ͨͩ͜͠Ε࣮ ͷ߹) ࠶ؼݺͼग़͠ͷʹݮগ͢Δύϥϝʔλͱ call_perm_ͷλϓϧ (call_perm_level) Λ measure ͱ͢Δ ࠶ؼΛߏ͢Δશͯͷؔ 14 ͷࣄલ݅ʹɺ࠶ؼΛߏ͢Δશͯͷؔ ͷதͰ࠷େͷؔͷ call_perm_level ΛՃ͢Δ ࠶ؼΛߏ͢ΔؔΛϔομϑΝΠϧ͔Βެ։͢Δ߹ɺ͜ΕΛ ެ։ͤͣϥούʔΛఏڙ͠ɺ͜ΕΛެ։͢ΔΑ͏ʹ͢Δ (͜ΕʹΑͬ ͯࣄલ͕݅ෳࡶԽͤͣʹࡁΉ) 14͜͜Ͱ isEven ͱ isOdd 2018/01/20 VeriFast Termination Checking 61 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ Dynamic Binding ύλʔϯ Dynamic Binding ಈతʹଋറ͞Εͨؔݺͼग़͕͠ (Ұൠʹ) ૬ޓ࠶ؼ͢Δύλʔϯɻ ؔϙΠϯλΛड͚औΓɺ͜ΕΛݺͼग़͢߹ɻ͕ؔ͞ΕΔͷ͔ಈ తʹܾ·ΔͷͰ༻ଆ (ϙΠϯλΛड͚औΔଆ) ʹ໌Β͔Ͱͳ͍ɻ Java ͷ߹நԽ͞ΕͨΠϯλʔϑΣʔεΦϒδΣΫτΛड͚औΓɺͦ ͷެ։͢ΔϝιουΛ༻͢Δ߹ʹ૬͢Δɻ 2018/01/20 VeriFast Termination Checking 62 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ Dynamic Binding ύλʔϯ Dynamic Binding ͷྫ ྫͱͯ͠ࢀরจதͷɺΦϒδΣΫτͷදࣜ͢ͷඍΛܭࢉ͢ΔྫͷҰ෦ Λ༻͢Δɻ (pseudo) interface RealFunc { float apply(float x); } class Math { static float derivative(RealFunc f, float x) { f.apply(x+1) - f.apply(x) } } class Identity implements RealFunc { float apply(float x) { x } } 2018/01/20 VeriFast Termination Checking 63 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ Dynamic Binding ύλʔϯ ΠϯλʔϑΣʔεఆٛ ҎԼΠϯλʔϑΣʔεΛද͢ܕͷఆٛΛ͍ࣔͯ͠Δɻ struct realfunc_obj { real_func * invoke; // object method //@ predicate(realfunc_obj *) RealFunc; }; /*@ predicate realfunc_obj(realfunc_obj * object , void * invoke , predicate(realfunc_obj *) p) = object ->invoke |-> invoke &*& object ->RealFunc |-> p &*& [_] is_real_func(invoke , p) &*& p(object ); @*/ 2018/01/20 VeriFast Termination Checking 64 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ Dynamic Binding ύλʔϯ ΠϯλʔϑΣʔεఆٛ ҎԼΠϯλʔϑΣʔεΛද͢ܕͷఆٛΛ͍ࣔͯ͠Δɻ real_func ύϥ ϝʔλ͖ͷؔܕɻ ΦϒδΣΫτϝιουͷγάωνϟ typedef double real_func /*@(predicate(realfunc_obj *) RealFunc)@*/ (realfunc_obj * object , double x); //@ requires realfunc_obj(object , this , RealFunc ); //@ ensures realfunc_obj(object , this , RealFunc ); 2018/01/20 VeriFast Termination Checking 64 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ Dynamic Binding ύλʔϯ Identity ΦϒδΣΫτͷߏங realfunc_obj * create_identity (void) //@ requires emp; //@ ensures realfunc_obj(result , identity , @identity ); { realfunc_obj * obj = malloc(sizeof(realfunc_obj )); if (!obj) abort (); obj ->invoke = identity; //@ obj ->RealFunc = @identity; /*@ produce_function_pointer_chunk real_func (identity )( @identity )(object , x) { call (); } @*/ //@ close identity(obj); return obj; //@ close realfunc_obj(obj , identity , @identity ); } 2018/01/20 VeriFast Termination Checking 65 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ Dynamic Binding ύλʔϯ apply ϝιουͷ࣮ apply ͷ࣮ double realfunc_object_apply (realfunc_obj * obj , double x) //@ requires realfunc_obj(obj , _, _); //@ ensures realfunc_obj(obj , _, _); { //@ open realfunc_obj(obj , _, _); real_func * invoke = obj ->invoke; //@ close realfunc_obj(obj , invoke , _); return invoke(obj , x); } 2018/01/20 VeriFast Termination Checking 66 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ Dynamic Binding ύλʔϯ Start Termchecking ͜͜·Ͱ͖ࣔͯͨ͠ΦϒδΣΫτΛ༻͢ΔؔͷఀࢭੑΛݕূ͢Δɻ 2018/01/20 VeriFast Termination Checking 67 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ Dynamic Binding ύλʔϯ ΠϯόϦΞϯτΛ֦ு ಉҰΠϯλʔϑΣʔεΛ͍࣋ͬͯͯΦϒδΣΫτຖʹ࣮͕ҟͳΓ͏Δ ͨΊɺͦͷ call_perm_ͦΕͧΕҟͳΔɻ͜ΕΛอ࣋͢ΔͨΊɺΦϒδΣ ΫτͷΠϯόϦΞϯτΛ֦ு͢Δɻ struct realfunc_obj { real_func * invoke; // object method //@ predicate(realfunc_obj*, list <void*>) RealFunc; }; /*@ predicate realfunc_obj(realfunc_obj * object , void * invoke , predicate(realfunc_obj*, list <void*>) p , list <void*> d) = object ->invoke |-> invoke &*& object ->RealFunc |-> p &*& [_] is_real_func(invoke , p) &*& p(object , ?d_) &*& bag_le(func_lt , cons(invoke , d_), d) == true; @*/ 2018/01/20 VeriFast Termination Checking 68 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ Dynamic Binding ύλʔϯ ΠϯόϦΞϯτΛ֦ு ݺͿؔΛྻڍग़དྷΔΑ͏ʹ list<void*>Λࢦఆɻ͜ͷ૿ͨ͠ύϥϝʔλ ͷ͜ͱΛ dynamic depth ͱݺͿɻ typedef double real_func /*@(predicate(realfunc_obj*, list <void*>) p)@*/ (realfunc_obj * object , double x); /*@ requires [?f]realfunc_obj(object , this , p, ?d) &*& call_perm(d); @*/ //@ ensures [f] realfunc_obj(object , this , p, d); //@ terminates; 2018/01/20 VeriFast Termination Checking 68 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ Dynamic Binding ύλʔϯ call permission ͷ্ք ֦ுͨ͠ΠϯόϦΞϯτʹɺग़དྷΔ͚ͩେ͖͍ call permission ͕͑ ΔΑ͏ʹ͍ͨ͠ɻ ίϯετϥΫλͷؔ (ͷ call_perm) Λ্ݶͱ͢Δ ݺͼ͍ͨؔΛશͯՃ͢Δ 2018/01/20 VeriFast Termination Checking 69 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ Dynamic Binding ύλʔϯ ίϯετϥΫλͷ permission Identity ΦϒδΣΫτͷίϯετϥΫλΛҎԼͷΑ͏ʹ֦ு͢Δɻ realfunc_obj * create_identity (void) /*@ requires call_perm_below (?d) &*& func_bag_lt ({ create_identity }, d) == true; @*/ /*@ ensures realfunc_obj(result , identity , @identity , { create_identity }); @*/ //@ terminates; { //... } 2018/01/20 VeriFast Termination Checking 70 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ Dynamic Binding ύλʔϯ Dynamic Binding ͷݕূखॱ Dynamic Binding ύλʔϯͷݕূखॱΛ·ͱΊΔɻ ΦϒδΣΫτͷΠϯόϦΞϯτΛ֦ு͠ɺdynamic depth ͱݺΕΔؔ ϙΠϯλϦετΛՃ͢Δ ग़དྷΔ͚ͩେ͖͍ call_perm Λࢦఆ͢ΔͨΊɺίϯετϥΫτͨؔ͠ ࣗͷ call_perm_Λ্ݶͱͯ͠͏ ΦϒδΣΫτͷؔͰݺͿؔͷ call_perm_શͯ dynamic depth ʹ join ͢Δ 2018/01/20 VeriFast Termination Checking 71 / 74 -
࣍ VeriFast ֓ཁ ఀࢭੑݕࠪͱԿ͔ VeriFast ʹΑΔఀࢭੑݕࠪ fixpoint ͷఀࢭੑ C ݴޠؔͷఀࢭੑݕࠪ
ύλʔϯผఀࢭੑݕূ Dynamic Binding ύλʔϯ ·ͱΊ ͜ͷষͰҎԼͷ 3 ͭͷύλʔϯʹ͍ͭͯఀࢭੑΛݕࠪ͢Δํͱ۩ମྫ Λ͖ࣔͯͨ͠ɻ Upcalls Only ύλʔϯ Static Recursion ύλʔϯ Dynamic Binding ύλʔϯ ͲͷύλʔϯͰ call_perm ͷେখؔͰઆ໌ͱݕূ͕ग़དྷͨɻ 2018/01/20 VeriFast Termination Checking 72 / 74 -
ࢀߟࢿྉ 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 Ԡ༻ ఀࢭੑݕࠪఀࢭ͢Δ͜ͱҎ֎ͷݕূʹԠ༻ग़དྷΔݟࠐΈ͕͋Δɻ ฒߦϓϩάϥϜ͕ఀࢭ͢Δͱ͍͏͜ͱ͔Β deadlock free Λূ໌͢Δ ఀࢭ͠ͳ͍͜ͱΛड़Δ͜ͱͰ liveness Λূ໌͢Δ
2018/01/20 VeriFast Termination Checking 74 / 74