From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,WEIRD_PORT autolearn=unavailable autolearn_force=no version=3.4.4 X-Received: by 10.200.3.196 with SMTP id z4mr5939429qtg.25.1502308078000; Wed, 09 Aug 2017 12:47:58 -0700 (PDT) X-Received: by 10.36.121.216 with SMTP id z207mr399493itc.4.1502308077945; Wed, 09 Aug 2017 12:47:57 -0700 (PDT) Path: eternal-september.org!reader01.eternal-september.org!reader02.eternal-september.org!news.eternal-september.org!news.eternal-september.org!feeder.eternal-september.org!border1.nntp.ams1.giganews.com!nntp.giganews.com!peer02.ams1!peer.ams1.xlned.com!news.xlned.com!peer03.am4!peer.am4.highwinds-media.com!peer03.iad!feed-me.highwinds-media.com!news.highwinds-media.com!w51no1779919qtc.0!news-out.google.com!1ni3262itx.0!nntp.google.com!u14no1935284ita.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail Newsgroups: comp.lang.ada Date: Wed, 9 Aug 2017 12:47:57 -0700 (PDT) In-Reply-To: <87twddw0i4.fsf@mid.deneb.enyo.de> Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=91.68.244.214; posting-account=T8VIJwoAAAA-IUorDdqOSpjmb16opbau NNTP-Posting-Host: 91.68.244.214 References: <87poo1a57p.fsf@mid.deneb.enyo.de> <87twddw0i4.fsf@mid.deneb.enyo.de> User-Agent: G2/1.0 MIME-Version: 1.0 Message-ID: Subject: Re: SPARK and integer arithmetic From: moy@adacore.com Injection-Date: Wed, 09 Aug 2017 19:47:57 +0000 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Received-Bytes: 4432 X-Received-Body-CRC: 2267973645 Xref: news.eternal-september.org comp.lang.ada:47662 Date: 2017-08-09T12:47:57-07:00 List-Id: Hi Florian, Sorry for jumping in so late in the game, I just discovered your discussion= yesterday. The problem you have with your specification is that it mixes m= odular integers with signed integers. These do not mix so easily with the p= rovers we currently ship with GNATprove: with CVC4 and Z3, modular types ar= e converted into bitvectors and signed integers into mathematical integers;= with Alt-Ergo both are converted into mathematical integers, with modulo o= perations where needed. In both cases, provers have difficulties dealing wi= th the mix.=20 An easier solution here is to use 64 bits modular types as a proxy type for= infinite precision integer type, given that you deal with operations that = cannot exceed the bounds of a 64 bits modular integer. That way, the transl= ation for CVC4 and Z3 is fully in bitvectors, so you have a chance to get f= ully automatic proof. This is what I did, defining Address_Integer as follows: type Address_64 is mod 2**64; subtype Address_Integer is Address_64 range 0 .. Address_64(Address'Last= ); Then, GNATprove produces an interesting counterexample for your postconditi= on: sum.ads:26:19: medium: postcondition might fail, cannot prove Address_Insid= e_Object'Result =3D ((L.L_Addr <=3D Addr) and (Address_Integer (Addr) < (Ad= dress_Integer (L.L_Addr) + Address_Integer (L.P_Vaddr) + L.P_Memsz (e.g. wh= en Addr =3D 1934972246 and Address_Inside_Object'Result =3D False and L =3D= (L_Addr =3D> 0, P_Vaddr =3D> 3254779904, P_Memsz =3D> 234881024)) You can copy-paste these values inside a test: with Sum; use Sum; procedure Test_Sum is Addr : Address :=3D 1934972246; L : Link_Map :=3D (L_Addr =3D> 0, P_Vaddr =3D> 3254779904, P_Memsz =3D= > 234881024); B : Boolean; begin B :=3D Address_Inside_Object (L, Addr); end Test_Sum; and check that indeed these values violate the postcondition: $ ./test_sum=20 raised SYSTEM.ASSERTIONS.ASSERT_FAILURE : failed postcondition from sum.a= ds:26 The problem is that your first inequality is not the correct one, you're mi= ssing the addition of L.P_Vaddr (which you do correctly in the C version yo= u point to in another thread). Here is a correct version of your postcondit= ion: with Post =3D> Address_Inside_Object'Result =3D ((Address_Integer (L.L_Addr) + Address_Integer (L.P_Vaddr) <=3D = Address_Integer(Addr)) and (Address_Integer (Addr) < (Address_Integer (L.L_Addr) + Address_Integer (L.P_Vaddr= ) + Address_Integer (L.P_Memsz)))); This version is proved automatically by GNATprove (although with a large ti= meout): sum.ads:26:19: info: postcondition proved (CVC4: 2 VC in max 4.8 seconds an= d 6546 steps; Z3: 1 VC in max 76.5 seconds and 247567 steps) I think we could also get GNATprove to prove your original specification, b= ut this will require more effort to guide the proof through ghost code, pos= sibly requiring combination of SMT solvers and static analysis, similar to = what we did in this paper: http://www.spark-2014.org/entries/detail/researc= h-corner-floating-point-computations-in-spark Let us know if you do other similar experiments with SPARK!