<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE article PUBLIC "-//NLM//DTD JATS (Z39.96) Journal Publishing DTD v1.3 20210610//EN" "JATS-journalpublishing1-3.dtd">
<article article-type="research-article" dtd-version="1.3" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xml:lang="ru"><front><journal-meta><journal-id journal-id-type="publisher-id">mais</journal-id><journal-title-group><journal-title xml:lang="ru">Моделирование и анализ информационных систем</journal-title><trans-title-group xml:lang="en"><trans-title>Modeling and Analysis of Information Systems</trans-title></trans-title-group></journal-title-group><issn pub-type="ppub">1818-1015</issn><issn pub-type="epub">2313-5417</issn><publisher><publisher-name>Yaroslavl State University</publisher-name></publisher></journal-meta><article-meta><article-id pub-id-type="doi">10.18255/1818-1015-2018-5-491-505</article-id><article-id custom-type="elpub" pub-id-type="custom">mais-745</article-id><article-categories><subj-group subj-group-type="heading"><subject>Research Article</subject></subj-group><subj-group subj-group-type="section-heading" xml:lang="ru"><subject>Материалы конференции</subject></subj-group><subj-group subj-group-type="section-heading" xml:lang="en"><subject>Conference Papers</subject></subj-group></article-categories><title-group><article-title>Автоматизация верификации C-программ с использованием символического метода элиминации инвариантов циклов</article-title><trans-title-group xml:lang="en"><trans-title>The Automation of C Program Verification by Symbolic Method of Loop Invariants Elimination</trans-title></trans-title-group></title-group><contrib-group><contrib contrib-type="author" corresp="yes"><contrib-id contrib-id-type="orcid">https://orcid.org/0000-0002-9387-6735</contrib-id><name-alternatives><name name-style="eastern" xml:lang="ru"><surname>Кондратьев</surname><given-names>Дмитрий Александрович</given-names></name><name name-style="western" xml:lang="en"><surname>Kondratyev</surname><given-names>Dmitry</given-names></name></name-alternatives><bio xml:lang="ru"><p>аспирант.</p><p>Новосибирск.</p></bio><bio xml:lang="en"><p> postgraduate student.</p><p>Novosibirsk.</p></bio><email xlink:type="simple">apple-66@mail.ru</email><xref ref-type="aff" rid="aff-1"/></contrib><contrib contrib-type="author" corresp="yes"><contrib-id contrib-id-type="orcid">https://orcid.org/0000-0002-2497-6484</contrib-id><name-alternatives><name name-style="eastern" xml:lang="ru"><surname>Марьясов</surname><given-names>Илья Владимирович</given-names></name><name name-style="western" xml:lang="en"><surname>Maryasov</surname><given-names>Ilya</given-names></name></name-alternatives><bio xml:lang="ru"><p>канд. физ.-мат. наук.</p><p>Новосибирск.</p></bio><bio xml:lang="en"><p> PhD.</p><p>Novosibirsk.</p></bio><email xlink:type="simple">ivm@iis.nsk.su</email><xref ref-type="aff" rid="aff-1"/></contrib><contrib contrib-type="author" corresp="yes"><contrib-id contrib-id-type="orcid">https://orcid.org/0000-0003-1364-5281</contrib-id><name-alternatives><name name-style="eastern" xml:lang="ru"><surname>Непомнящий</surname><given-names>Валерий Александрович</given-names></name><name name-style="western" xml:lang="en"><surname>Nepomniaschy</surname><given-names>Valery</given-names></name></name-alternatives><bio xml:lang="ru"><p>канд. физ.-мат. наук.</p><p>Новосибирск.</p></bio><bio xml:lang="en"><p>PhD.</p><p>Novosibirsk.</p></bio><email xlink:type="simple">vnep@iis.nsk.su</email><xref ref-type="aff" rid="aff-2"/></contrib></contrib-group><aff-alternatives id="aff-1"><aff xml:lang="ru"><institution>Институт систем информатики им. А.П. Ершова СО РАН.</institution><country>Россия</country></aff><aff xml:lang="en"><institution>A.P. Ershov Institute of Informatics Systems SB RAS.</institution><country>Russian Federation</country></aff></aff-alternatives><aff-alternatives id="aff-2"><aff xml:lang="ru"><institution>Институт систем информатики им. А.П. Ершова СО РАН.</institution><country>Россия</country></aff><aff xml:lang="en"><institution>A.P. Ershov Institute of Informatics Systems SB RAS</institution><country>Russian Federation</country></aff></aff-alternatives><pub-date pub-type="collection"><year>2018</year></pub-date><pub-date pub-type="epub"><day>28</day><month>10</month><year>2018</year></pub-date><volume>25</volume><issue>5</issue><fpage>491</fpage><lpage>505</lpage><permissions><copyright-statement>Copyright &amp;#x00A9; Кондратьев Д.А., Марьясов И.В., Непомнящий В.А., 2018</copyright-statement><copyright-year>2018</copyright-year><copyright-holder xml:lang="ru">Кондратьев Д.А., Марьясов И.В., Непомнящий В.А.</copyright-holder><copyright-holder xml:lang="en">Kondratyev D., Maryasov I., Nepomniaschy V.</copyright-holder><license xml:lang="ru" license-type="creative-commons-attribution" xlink:href="https://creativecommons.org/licenses/by/4.0/" xlink:type="simple"><license-p>Данная работа распространяется под лицензией Creative Commons Attribution 4.0.</license-p></license><license xml:lang="en" license-type="creative-commons-attribution" xlink:href="https://creativecommons.org/licenses/by/4.0/" xlink:type="simple"><license-p>This work is licensed under a Creative Commons Attribution 4.0 License.</license-p></license></permissions><self-uri xlink:href="https://www.mais-journal.ru/jour/article/view/745">https://www.mais-journal.ru/jour/article/view/745</self-uri><abstract><p>При дедуктивной верификации программ, написанных на императивных языках программирования, особую сложность вызывает порождение и доказательство условий корректности, соответствующих циклам, поскольку каждый из них должен быть снабжён инвариантом, построение которого часто является нетривиальной задачей. Методы синтеза инвариантов циклов, как правило, носят эвристический характер, что затрудняет их применение. Альтернативой является символический метод элиминации инвариантов циклов, предложенный В.А. Непомнящим в 2005 году. Его идея состоит в представлении тела цикла в виде специальной операции замены при выполнении определённых ограничений. Такая операция в символической форме выражает действие цикла, что позволяет ввести в аксиоматическую семантику правило вывода для циклов, не использующее инварианты. В данной работе представлено дальнейшее развитие этого метода. Он расширяет метод смешанной аксиоматической семантики, предложенный для верификации C-light программ. Данное расширение включает в себя метод верификации итераций над изменяемыми массивами с возможным выходом из тела цикла в C-light программах. Метод содержит правило вывода для итерации без инвариантов циклов. Данное правило было реализовано в генераторе условий корректности, являющемся частью системы автоматизированной верификации C-light программ. Для проведения автоматического доказательства в используемой системе ACL2 были разработаны и реализованы два алгоритма: первый порождает операцию замены на языке системы ACL2, а второй генерирует вспомогательные леммы, позволяющие системе ACL2 успешно доказать получаемые условия корректности в автоматическом режиме. Применение вышеуказанных методов и алгоритмов проиллюстрировано примером.</p></abstract><trans-abstract xml:lang="en"><p>During deductive verification of programs written in imperative languages, the generation and proof of verification conditions corresponding to loops can cause difficulties, because each one must be provided with an invariant whose construction is often a challenge. As a rule, the methods of invariant synthesis are heuristic ones. This impedes its application. An alternative is the symbolic method of loop invariant elimination suggested by V.A. Nepomniaschy in 2005. Its idea is to represent a loop body in a form of special replacement operation under certain constraints. This operation expresses loop effect in a symbolic form and allows to introduce an inference rule which uses no invariants in axiomatic semantics. This work represents the further development of this method. It extends the mixed axiomatic semantics method suggested for C-light program verification. This extension includes the verification method of iterations over changeable arrays possibly with loop exit in C-light programs. The method contains the inference rule for iterations without loop invariants. This rule was implemented in verification conditions generator which is a part of the automated system of C-light program verification. To prove verification conditions automatically in ACL2, two algorithms were developed and implemented. The first one automatically generates the replacement operation in ACL2 language, the second one automatically generates auxiliary lemmas which allow to prove the obtained verification conditions in ACL2 successfully in automatic mode. An example which illustrates the application of the mentioned methods is described.</p></trans-abstract><kwd-group xml:lang="ru"><kwd>Си-лайт</kwd><kwd>инварианты циклов</kwd><kwd>смешанная аксиоматическая семантика</kwd><kwd>финитная итерация</kwd><kwd>массивы</kwd><kwd>ACL2</kwd><kwd>спецификация</kwd><kwd>верификация</kwd><kwd>логика Хоара</kwd></kwd-group><kwd-group xml:lang="en"><kwd>C-light</kwd><kwd>loop invariants</kwd><kwd>mixed axiomatic semantics</kwd><kwd>definite iteration</kwd><kwd>arrays</kwd><kwd>ACL2</kwd><kwd>specification</kwd><kwd>verification</kwd><kwd>Hoare logic</kwd></kwd-group><funding-group><funding-statement xml:lang="ru">РФФИ № 17-01-00789</funding-statement><funding-statement xml:lang="en">RFBR, grant 17-01-00789</funding-statement></funding-group></article-meta></front><back><ref-list><title>References</title><ref id="cit1"><label>1</label><citation-alternatives><mixed-citation xml:lang="ru">Anureev I. S., Maryasov I. V., Nepomniaschy V. A., “C-programs Verification Based on Mixed Axiomatic Semantics”, Automatic Control and Computer Sciences, 45:7 (2011), 485–500.</mixed-citation><mixed-citation xml:lang="en">Anureev I. S., Maryasov I. V., Nepomniaschy V. A., “C-programs Verification Based on Mixed Axiomatic Semantics”, Automatic Control and Computer Sciences, 45:7 (2011), 485–500.</mixed-citation></citation-alternatives></ref><ref id="cit2"><label>2</label><citation-alternatives><mixed-citation xml:lang="ru">Cohen E., Dahlweid M., Hillebrand M., Leinenbach D., Moskal M., Santen T., Schulte W., Tobies S., “VCC: A Practical System for Verifying Concurrent C”, 22nd Int. Conf. TPHOLs, LNCS, 5674 (2009), 23–42.</mixed-citation><mixed-citation xml:lang="en">Cohen E., Dahlweid M., Hillebrand M., Leinenbach D., Moskal M., Santen T., Schulte W., Tobies S., “VCC: A Practical System for Verifying Concurrent C”, 22nd Int. Conf. TPHOLs, LNCS, 5674 (2009), 23–42.</mixed-citation></citation-alternatives></ref><ref id="cit3"><label>3</label><citation-alternatives><mixed-citation xml:lang="ru">Dongarra J. J., van der Steen A. J., “High-performance computing systems: Status and outlook”, Acta Numerica, 21 (2012), 379–474.</mixed-citation><mixed-citation xml:lang="en">Dongarra J. J., van der Steen A. J., “High-performance computing systems: Status and outlook”, Acta Numerica, 21 (2012), 379–474.</mixed-citation></citation-alternatives></ref><ref id="cit4"><label>4</label><citation-alternatives><mixed-citation xml:lang="ru">Filliˆatre J.-C., March´e C., “Multi-prover Verification of C Programs”, 6th ICFEM, LNCS, 3308 (2004), 15–29.</mixed-citation><mixed-citation xml:lang="en">Filliˆatre J.-C., March´e C., “Multi-prover Verification of C Programs”, 6th ICFEM, LNCS, 3308 (2004), 15–29.</mixed-citation></citation-alternatives></ref><ref id="cit5"><label>5</label><citation-alternatives><mixed-citation xml:lang="ru">Jacobs B., Kiniry J. L., Warnier M., “Java Program Verification Challenges”, FMCO 2002, LNCS, 2852 (2003), 202–219.</mixed-citation><mixed-citation xml:lang="en">Jacobs B., Kiniry J. L., Warnier M., “Java Program Verification Challenges”, FMCO 2002, LNCS, 2852 (2003), 202–219.</mixed-citation></citation-alternatives></ref><ref id="cit6"><label>6</label><citation-alternatives><mixed-citation xml:lang="ru">Kaufmann M., Moore J.S., “An Industrial Strength Theorem Prover for a Logic Based on Common Lisp”, IEEE Transactions on Software Engineering, 23:4 (1997), 203–213.</mixed-citation><mixed-citation xml:lang="en">Kaufmann M., Moore J.S., “An Industrial Strength Theorem Prover for a Logic Based on Common Lisp”, IEEE Transactions on Software Engineering, 23:4 (1997), 203–213.</mixed-citation></citation-alternatives></ref><ref id="cit7"><label>7</label><citation-alternatives><mixed-citation xml:lang="ru">Kondratyev D., “Implementing the Symbolic Method of Verification in the C-Light Project”, PSI 2017, LNCS, 10742 (2018), 227–240.</mixed-citation><mixed-citation xml:lang="en">Kondratyev D., “Implementing the Symbolic Method of Verification in the C-Light Project”, PSI 2017, LNCS, 10742 (2018), 227–240.</mixed-citation></citation-alternatives></ref><ref id="cit8"><label>8</label><citation-alternatives><mixed-citation xml:lang="ru">Kondratyev D.A., “Towards Loop Invariant Elimination for Definite Iterations over Changeable Data Structures in C Programs Verification. Appendices”, https:// bitbucket.org/c-light/loop-invariant-elimination.</mixed-citation><mixed-citation xml:lang="en">Kondratyev D.A., “Towards Loop Invariant Elimination for Definite Iterations over Changeable Data Structures in C Programs Verification. Appendices”, https:// bitbucket.org/c-light/loop-invariant-elimination.</mixed-citation></citation-alternatives></ref><ref id="cit9"><label>9</label><citation-alternatives><mixed-citation xml:lang="ru">Kondratyev D.A., Maryasov I.V., Nepomniaschy V.A., “Towards Loop Invariant Elimination for Definite Iterations over Changeable Data Structures in C Programs Verification”, PSSV 2018, Workshop Proceedings, Yaroslavl, 2018, 51–57.</mixed-citation><mixed-citation xml:lang="en">Kondratyev D.A., Maryasov I.V., Nepomniaschy V.A., “Towards Loop Invariant Elimination for Definite Iterations over Changeable Data Structures in C Programs Verification”, PSSV 2018, Workshop Proceedings, Yaroslavl, 2018, 51–57.</mixed-citation></citation-alternatives></ref><ref id="cit10"><label>10</label><citation-alternatives><mixed-citation xml:lang="ru">Li J., Sun J., Li L., Loc Le Q., Lin S-W., “Automatic Loop Invariant Generation and Refinement through Selective Sampling”, 32nd IEEE/ACM International Conference on Automated Software Engineering (ASE), 2017, 782–792.</mixed-citation><mixed-citation xml:lang="en">Li J., Sun J., Li L., Loc Le Q., Lin S-W., “Automatic Loop Invariant Generation and Refinement through Selective Sampling”, 32nd IEEE/ACM International Conference on Automated Software Engineering (ASE), 2017, 782–792.</mixed-citation></citation-alternatives></ref><ref id="cit11"><label>11</label><citation-alternatives><mixed-citation xml:lang="ru">Maryasov I.V., Nepomniaschy V.A., “Loop Invariants Elimination for Definite Iterations over Unchangeable Data Structures in C Programs”, Modeling and Analysis of Information Systems, 22:6 (2015), 773–782.</mixed-citation><mixed-citation xml:lang="en">Maryasov I.V., Nepomniaschy V.A., “Loop Invariants Elimination for Definite Iterations over Unchangeable Data Structures in C Programs”, Modeling and Analysis of Information Systems, 22:6 (2015), 773–782.</mixed-citation></citation-alternatives></ref><ref id="cit12"><label>12</label><citation-alternatives><mixed-citation xml:lang="ru">Maryasov I.V., Nepomniaschy V.A., Kondratyev D.A., “Invariant Elimination of Definite Iterations over Arrays in C Programs Verification”, Modeling and Analysis of Information Systems, 24:6 (2017), 743–754.</mixed-citation><mixed-citation xml:lang="en">Maryasov I.V., Nepomniaschy V.A., Kondratyev D.A., “Invariant Elimination of Definite Iterations over Arrays in C Programs Verification”, Modeling and Analysis of Information Systems, 24:6 (2017), 743–754.</mixed-citation></citation-alternatives></ref><ref id="cit13"><label>13</label><citation-alternatives><mixed-citation xml:lang="ru">Maryasov I.V., Nepomniaschy V.A., Promsky A.V., Kondratyev D.A., “Automatic C Program Verification Based on Mixed Axiomatic Semantics”, Automatic Control and Computer Sciences, 48:7 (2014), 407–414.</mixed-citation><mixed-citation xml:lang="en">Maryasov I.V., Nepomniaschy V.A., Promsky A.V., Kondratyev D.A., “Automatic C Program Verification Based on Mixed Axiomatic Semantics”, Automatic Control and Computer Sciences, 48:7 (2014), 407–414.</mixed-citation></citation-alternatives></ref><ref id="cit14"><label>14</label><citation-alternatives><mixed-citation xml:lang="ru">Nepomniaschy V.A., “Symbolic Method of Verification of Definite Iterations over Altered Data Structures”, Programming and Computer Software, 31:1 (2005), 1–9.</mixed-citation><mixed-citation xml:lang="en">Nepomniaschy V.A., “Symbolic Method of Verification of Definite Iterations over Altered Data Structures”, Programming and Computer Software, 31:1 (2005), 1–9.</mixed-citation></citation-alternatives></ref><ref id="cit15"><label>15</label><citation-alternatives><mixed-citation xml:lang="ru">Tuerk T., “Local Reasoning about While-Loops”, VSTTE 2010, Workshop Proceedings, 2010, 29–39.</mixed-citation><mixed-citation xml:lang="en">Tuerk T., “Local Reasoning about While-Loops”, VSTTE 2010, Workshop Proceedings, 2010, 29–39.</mixed-citation></citation-alternatives></ref></ref-list><fn-group><fn fn-type="conflict"><p>The authors declare that there are no conflicts of interest present.</p></fn></fn-group></back></article>
