新闻开发人员企业区块链解释事件和会议新闻时事通讯
订阅我们的新闻.
电子邮件地址
我们尊重您的隐私
主页博客开发人员
在我的编码之旅中拥抱形式方法的力量:我如何成为一名达夫尼传教士
由ConsenSys 2020年12月22日发布于2020年12月22日
乔安妮·富勒(Joanne Fuller)
首先,我想写这篇博客文章是希望其他人能体验到我在学习过程中所经历的顿悟时刻。 达夫尼 作为我探索的一部分 形式方法. 此外,我希望这个职位能够促使其他人将正式方法视为任何编写代码的人中的关键和必要技能。作为一部分 R中的自动验证团队&D在ConsenSys, 我在以太坊2阶段0规范的形式验证中使用Dafny,我想分享为什么我觉得它有用.
我的背景
我应该明确说明自己不是软件开发人员,而是将自己视为具有一定软件开发知识的数学程序员。在高中的最后一年,我第一次学习写程序,这是我数学课的一部分,也许我应该提一提,尽管我当时很喜欢使用计算机,但是学习如何编程的前景使我几乎感到恐惧。放弃了那个特定的数学课。决定面对自己对失败的恐惧(在学习编程方面,并有可能破坏我在这堂课中的学习成绩),因此我继续在编程的背景下经历了自己的第一个顿悟时刻。我仍然可以生动地记得坐在教室里,并意识到编写一个解决数学问题的程序并不是一个神奇而神秘的过程,这就像在写下我如何解决脑中的问题一样。之后没有回头路了!
从那以后,编程一直是我所做的一切的重要方面。我在密码学领域的博士学位主要依赖于开发算法然后对最佳实现进行编程的能力。我的程序是为实验而编写的,尽管我没有进行现在称为正式测试的工作,但我还是会使用有关预期输出的逻辑推理来非正式地检查范围和测试用例。我也曾在金融和经济学领域从事多年的学术研究工作。再次包括编写程序,然后我再次使用自己的技术对它们的正确性进行非正式测试和推理.
可以说,尽管我很欣赏这样的事实,即测试不可能总是对每个案例进行测试,但测试始终是不完整的。我有足够的信心相信,以严格的方式进行非正式测试时,我的数学思维方式非常好。因此,我绝对不完全了解测试和证明正确性之间的区别,也不了解其后果!在加入ConsenSys之前的职业生涯中,我很满足于依靠自己的非正式技术来通过测试确定我认为正确的内容.
因此,我的背景是故事的一部分,因为我自己对之前没有发现正式方法感到有些惊讶。我认为自己是数学家;我喜欢数学,算法和逻辑。现在,仅依靠不完整的测试似乎很疯狂,但是对于那些编程的人,至少对某种形式化方法可以提供什么以及由于计算机程序采用的多种方式而遗漏错误的潜在后果一无所知,这似乎也很疯狂。融入我们的生活。形式化方法使我们可以超越测试,以证明程序对包含前后条件的规范是正确的.
达夫尼的第一个例子
作为一个简单的例子,考虑非负红利n除以正除数d的整数;
n /天
如下图所示:
尽管在类型化的编程语言中我们可以在某种程度上限制输入参数,但这并不总是足够的。在此示例中,将n和d指定为自然数意味着这两个输入都必须是非负整数,但没有提供将d限制为正整数的条件。通过require语句使用前提条件提供了这样的限制,并且意味着仅当d > 0。因此,如果程序的任何其他部分将导致在不满足这样的前提条件的情况下调用div,则该程序将不会进行验证。然后suresure语句提供后置条件,并提供方法输出必须满足的正式规范.
这个示例是使用Dafny编写的:“一种用于功能正确性的语言和程序验证程序”,这使我想到了下一个要点,那就是为什么我如此喜欢Dafny。我认为可以公平地说,对于许多程序员而言,使用“正式方法”来验证程序正确性的想法有些令人恐惧,并且通常被认为“太”难了。是否由于缺乏对技术的了解,对收益的认识不足,甚至在这一领域缺乏培训;不管是什么原因,我相信Dafny能够让任何程序员在他们的工作中应用形式化方法时迅速取得成功。看上面的代码片段,我希望任何具有一定编程知识的人都能阅读此Dafny代码。 Dafny是非常程序员友好的语言。一旦您学习了一点点Dafny,就可以很容易地开始实验,然后随手进行基本学习。如果您有兴趣学习Dafny,那么一个不错的起点是 教程系列 由Microsoft。该站点还包括一个在线编辑器,因此很容易尝试本教程示例。这 验证角YouTube频道 是有用参考的另一个来源.
我的顿悟时刻
最后,我想分享我学习达芬妮时的顿悟时刻。我当然听过大型知名公司关于短而简单的代码片段的故事,这些错误遗漏了一些错误,最终造成了数百万美元的损失。但是我认为只有当您意识到自己无意识地在一个简单的函数中创建错误会变得多么容易时,这才是有道理的!当你对自己说:“哦,很容易犯这个错误!”
我的时刻来到了,而看着其中之一 验证角视频.
在本教程中,Rustan Leino通过了一个SumMax方法,该方法采用两个整数x和y,并分别返回总和和最大值,s和m。这个例子相对简单,Dafny代码如下所示.
通过键入将输入x和y指定为整数,并且不需要其他前提条件。这三个后置条件提供了检查,以确保输出确实符合规范,即s等于x + y,m等于x或y且m不超过x和y。然后,将SumMaxBackwards方法作为练习呈现,这在这里变得更加有趣。该规范与SumMax相反,即给定总和和最大值返回整数x和y。好的,因此第一次尝试可能具有相同的后置条件。因为输入和输出之间的关系仍然成立。如果我们让x为最大值,那么快速的代数告诉我们y应该等于和减去最大值。将其放入在线编辑器中可得到以下内容.
没有验证。那么出了什么问题呢?我们被告知后置条件不成立,特别是第3行上的后置条件(确保x<=米 && ÿ <= 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和m的输入限制为有效整数以使输出x和y满足规范的前提条件,否则我们的方法可能会产生错误的结果。为了提供有效的输入,我们需要在s和m之间建立什么关系?多一点的代数告诉我们 <= m * 2是x和y的有效解。如果我们将此作为前提条件,Dafny现在可以验证代码,如下所示.
在这个例子中,我可以看到将错误引入代码有多么容易。仅仅因为我们将输入参数的总和称为“ s”,将最大值称为“ m”,并不意味着将适当地调用该方法,因此,例如在某些较大的程序中,此操作可能会导致许多意想不到的后果错误类型。我希望它对其他更广泛地了解Dafny或形式方法的人有用.
我现在在做什么
好吧,这使我结束了文章的结尾。如果您想了解我目前与Dafny合作的内容,请查看此内容 GitHub回购. 我是R中自动验证小组的成员&D是ConsenSys的D,我们在以太坊2阶段0规范的正式验证中使用了Dafny。在区块链空间中使用形式化方法是ConsenSys激动人心的新研究领域,我鼓励有兴趣进一步了解Eth 2.0的任何人查看我们项目回购中的可用资源。.
订阅我们的时事通讯以获取最新的以太坊新闻,企业解决方案,开发人员资源以及更多信息。