Использование силы формальных методов в моем путешествии по программированию: как я стал евангелистом Dafny

блог 1НовостиДля разработчиковПредприятиеБлокчейн РазъяснениеМероприятия и конференцииПрессаИнформационные бюллетени

Подписывайтесь на нашу новостную рассылку.

Адрес электронной почты

Мы уважаем вашу конфиденциальность

ГлавнаяБлогДля разработчиков

Использование силы формальных методов в моем путешествии по программированию: как я стал евангелистом Dafny

by ConsenSys22 декабря, 2020Опубликовано 22 декабря, 2020

Снимок экрана 2020 12 15 at 6 46 32 pm 1

Джоанн Фуллер

Я хочу начать с того, что пишу этот пост в блоге в надежде, что другие смогут испытать момент прозрения, который у меня был во время обучения. Дафни как часть моего исследования в формальные методы. Кроме того, я надеюсь, что этот пост послужит катализатором для других, чтобы рассматривать формальные методы как критически важный и необходимый навык в арсенале любого, кто пишет код. В рамках Команда автоматической проверки в R&D в ConsenSys, Я использую Dafny для формальной проверки спецификации Ethereum 2 Phase 0 и хочу рассказать, почему я считаю его полезным.

Мой фон

Я должен прояснить, что я не разработчик программного обеспечения, а скорее считаю себя математическим программистом с некоторыми знаниями в области разработки программного обеспечения. Впервые я научился писать программы на уроке математики на последнем году обучения в старшей школе, и мне, вероятно, следует упомянуть, что, хотя в то время мне очень нравилось пользоваться компьютером, перспектива научиться программировать пугала меня до такой степени, что я почти бросил этот конкретный математический класс. Решив столкнуться со своим страхом неудачи (в отношении обучения программированию и потенциально испорченного результата в этом классе), я пережил свой первый момент прозрения в контексте программирования. Я до сих пор хорошо помню, как сидел в классе и осознавал, что написание программы для решения математической задачи не было каким-то волшебным и загадочным процессом, это было почти как записать, как я буду работать над проблемой в своей голове. После этого не было оглядки! 

Программирование было важным аспектом всего, что я делал с тех пор. Моя докторская степень в области криптографии во многом полагалась на способность разрабатывать алгоритмы, а затем программировать оптимальные реализации. Мои программы были написаны для экспериментов, и, хотя я не проводил то, что мы теперь называем формальным тестированием, я неофициально проверял границы и тестовые примеры, используя логические рассуждения о предполагаемых результатах. Я также много лет проработал академиком, занимаясь исследованиями в области финансов и экономики. Опять же, это включало написание программ, и снова я использовал свои собственные методы, чтобы неформально проверить и рассуждать об их правильности.. 

Будет справедливо сказать, что, хотя я ценил тот факт, что тестирование всегда будет неполным в том смысле, что невозможно проверить каждый случай; что я был достаточно уверен в том, что мой математический образ мышления был довольно хорош, когда дело касалось неформального строгого тестирования. Таким образом, я определенно не понимал ни разницы между тестированием и доказательством правильности, ни их последствий! В течение моей карьеры до прихода в ConsenSys я довольствовался тем, что полагался на свои собственные неформальные методы определения того, что я считал правильным, посредством тестирования.. 

Таким образом, мое прошлое является частью истории, так как я сам несколько удивлен, что раньше не открыл для себя формальных методов. Считаю себя математиком; Я люблю математику, алгоритмы и логику. Сейчас кажется безумием просто полагаться на неполное тестирование, но также кажется безумием, что любой, кто занимается программированием, не имеет хотя бы некоторой оценки того, что могут предложить формальные методы, и потенциальных последствий пропуска ошибки, учитывая множество способов, которыми компьютерные программы интегрированы в нашу жизнь. Формальные методы позволяют нам выйти за рамки тестирования, чтобы доказать, что программа соответствует спецификации, которая включает предварительные и последующие условия.. 

Первый пример Дафни

В качестве простого примера рассмотрим целочисленное деление неотрицательного делимого n на положительный делитель d; 


н / д

показано ниже:

Хотя в типизированном языке программирования мы можем несколько ограничить входные параметры, этого не всегда достаточно. В этом примере указание n и d как натуральных чисел означает, что оба ввода должны быть неотрицательными целыми числами, но не предусматривает ограничения d как положительного целого числа. Использование предварительного условия посредством оператора requires обеспечивает такое ограничение и означает, что этот метод может быть вызван только в том случае, если d > 0. Следовательно, если какая-либо другая часть программы вызовет вызов div без выполнения такого предварительного условия, программа не будет проверять. Затем оператор обеспечивает условие публикации и формальную спецификацию того, чему должны удовлетворять выходные данные метода..

Этот пример написан с использованием Dafny: «Средство проверки функциональной корректности языка и программы» и подводит меня к следующему пункту, а именно, почему я такой поклонник Dafny. Я думаю, будет справедливо сказать, что для многих программистов мысль об использовании «формальных методов» для проверки правильности программы несколько пугает и часто воспринимается как «слишком» трудная. Причина в том, что это недостаточное знакомство с методами, недостаточная оценка преимуществ или даже отсутствие обучения в этой области; какими бы ни были причины, я считаю, что Дафни может позволить любым программистам быстро добиться успеха в применении формальных методов в своей работе. Глядя на приведенный выше фрагмент кода, я ожидал, что любой, обладающий некоторыми знаниями в области программирования, сможет прочитать этот код Dafny; Дафни – очень удобный для программистов язык. Как только вы немного научитесь Дафни, очень легко начать экспериментировать, а затем, в основном, учиться на ходу. И если вы заинтересованы в изучении Дафни, отличное место для начала – это серия учебных пособий от Microsoft. На сайте также есть онлайн-редактор, так что очень легко опробовать учебные примеры. В Канал Verification Corner на YouTube еще один источник полезных ссылок.

Момент прозрения

Наконец, я хотел поделиться моментом прозрения, когда я изучал Дафни. Я определенно слышал истории о коротких и простых фрагментах кода от крупных уважаемых компаний, об ошибках, которые были пропущены и в конечном итоге стоили многие миллионы долларов; но я думаю, что только когда вы понимаете, насколько легко было бы непреднамеренно создать ошибку в простой функции, все это имеет смысл! Момент, когда вы говорите себе: «О, было бы так легко сделать эту ошибку!»

Мой момент наступил, когда я смотрел один из Verification Corner видео

В этом руководстве Рустан Лейно рассматривает метод SumMax, который принимает два целых числа, x и y, и возвращает сумму и max, s и m, соответственно. Этот пример относительно прост, и код Dafny показан ниже..

Входные данные x и y указываются как целые числа путем ввода, и никаких других предварительных условий не требуется. Три постусловия обеспечивают проверку того, что результат действительно соответствует спецификациям, а именно, что s действительно равно x + y, и что m равно либо x, либо y, и что m не превышает x и y. Затем метод SumMaxBackwards представлен как упражнение, и именно здесь он становится более интересным. Спецификация является обратной по отношению к SumMax, т.е. при заданной сумме и максимуме возвращаются целые числа x и y. Итак, первая попытка может быть с теми же постусловиями; поскольку отношения между входами и выходами все еще сохраняются. Если мы позволим x быть максимумом, то небольшой кусочек алгебры скажет нам, что y должно быть равно сумме минус максимум. Помещение этого в онлайн-редактор дает следующее.

Снимок экрана 2020 12 15 at 6 38 37 pm 1 Снимок экрана 2020 12 16 at 5 35 22 pm

Это не проверяет. Так что же пошло не так? Нам говорят, что постусловие не выполнено, и в частности постусловие в строке 3 (гарантирует, что x<= м && y <= m) может не выполняться. При более внимательном рассмотрении мы видим, что это условие публикации указывает, что x <= m и y <= м. Итак, мы знаем, что x меньше или равно m, поскольку мы устанавливаем x равным m, поэтому это означает, что y <= m часть не проверяется. Как такое могло случиться? Наша алгебра сказала нам, что y: = s – m. Допустим, s равно 5, а m равно 3, тогда y = 5–3 = 2, что гарантирует y <= м; но предположим, что мы вызываем этот метод с s, равным 5, и m, равным 1. Ничто не помешает нам вызвать метод с этими входными параметрами, но это вызовет проблему, так как y = 5 – 1 = 4, а затем y > м. По сути, мы видим, что даже несмотря на то, что входной параметр должен быть максимумом из двух целых чисел, которые создают сумму s, ничто не мешает нам вызвать метод с недопустимыми входными данными. Если не включено предварительное условие, ограничивающее входные данные s и m допустимыми целыми числами, которые приведут к выходным x и y, соответствующим спецификации, тогда наш метод может давать неверные результаты. Какие отношения нам нужны между s и m, чтобы обеспечить правильные входные данные? Немного больше алгебры показывает нам, что s <= m * 2, чтобы было действительное решение x и y. Если мы добавим это в качестве предварительного условия, Дафни теперь сможет проверить код, как показано ниже.. 

Снимок экрана 2020 12 15 at 6 46 32 pm 1 Снимок экрана 2020 12 16 в 5 37 39 пп

Это был пример, в котором я мог видеть, насколько легко ввести ошибку в код. Тот факт, что мы называем входные параметры ‘s’ для суммы и ‘m’ для максимума, не означает, что метод будет вызываться соответствующим образом и, как таковой, как часть какой-то более крупной программы, из этого может быть много непредвиденных последствий. тип ошибки. Я надеюсь, что это будет полезно для всех, кто узнает о Дафни или формальных методах в целом..

Над чем я сейчас работаю

Что ж, это подводит меня к концу моего поста. Если вы хотите увидеть, над чем я сейчас работаю с Дафни, посмотрите это Репозиторий GitHub. Я являюсь частью группы автоматической проверки в R&D в ConsenSys, и мы используем Dafny для формальной проверки спецификации Ethereum 2 Phase 0. Использование формальных методов в пространстве блокчейнов – это новая захватывающая область исследований, которая была охвачена ConsenSys, и я бы посоветовал всем, кто хочет узнать больше о Eth 2.0, взглянуть на ресурсы, доступные в нашем репозитории проектов..

Подпишитесь на нашу рассылку, чтобы получать последние новости Ethereum, корпоративные решения, ресурсы для разработчиков и многое другое.

Mike Owergreen Administrator
Sorry! The Author has not filled his profile.
follow me
Like this post? Please share to your friends:
Adblock
detector
map