코딩 여정에서 형식적 방법의 힘을 포용 : 어떻게 내가 Dafny 전도자가 되었는가

블로그 1뉴스 개발자 엔터프라이즈 블록 체인 설명 이벤트 및 컨퍼런스 보도 자료뉴스 레터

뉴스 레터 구독.

이메일 주소

우리는 귀하의 개인 정보를 존중합니다

홈 블로그 개발자

코딩 여정에서 형식적 방법의 힘을 포용 : 어떻게 내가 Dafny 전도자가 되었는가

by ConsenSys 12 월 22, 2020Posted on 12 월 22, 2020

스크린 샷 2020 12 15 at 6 46 32 pm 1

조앤 풀러

배우면서 겪었던 깨달음의 순간을 다른 사람들이 경험할 수 있기를 바라며이 글을 쓰고 있다고 말하면서 시작하고 싶습니다. Dafny 탐구의 일환으로 공식적인 방법. 또한이 게시물이 다른 사람들이 코드를 작성하는 모든 사람의 무기고 내에서 공식적인 방법을 중요하고 필요한 기술로 간주하는 촉매제 역할을 할 수 있기를 바랍니다. 의 일부로 R 내의 자동 검증 팀&ConsenSys의 D, Ethereum 2 Phase 0 사양의 공식 검증에 Dafny를 사용하고 있는데 왜 유용하다고 생각하는지 공유하고 싶습니다..

내 배경

나는 내가 소프트웨어 개발자가 아니라는 것을 분명히해야한다. 오히려 나는 소프트웨어 개발에 대한 지식을 가진 수학적 프로그래머라고 생각한다. 저는 고등학교 마지막 해에 수학 수업의 일환으로 프로그램을 작성하는 법을 처음 배웠습니다. 당시 컴퓨터 사용을 아주 좋아했지만 프로그래밍 방법을 배우게 될 것이라는 전망이 제가 거의 그 특정 수학 수업을 중단했습니다. (프로그래밍을 배우고이 수업에서 내 결과를 망칠 가능성이있는 것과 관련하여) 실패에 대한 두려움에 직면하기로 결정한 후, 나는 프로그래밍의 맥락에서 첫 번째 깨달음을 경험했습니다. 수업에 앉아 수학 문제를 풀기위한 프로그램을 작성하는 것이 마술적이고 신비한 과정이 아니라는 것을 깨달았 음을 아직도 생생하게 기억할 수 있습니다. 마치 내 머릿속의 문제를 어떻게 해결해야할지 적는 것과 같습니다. 그 후 돌아 보지 않았습니다! 

프로그래밍은 제가 그 이후로해온 모든 것의 중요한 측면이었습니다. 암호학 박사 학위는 알고리즘을 개발 한 다음 최적의 구현을 프로그래밍하는 능력에 크게 의존했습니다. 내 프로그램은 실험용으로 작성되었으며 이제 공식 테스트라고 부르는 작업을 수행하지는 않았지만 의도 한 출력에 대한 논리적 추론을 사용하여 경계와 테스트 케이스를 비공식적으로 확인했습니다. 저는 또한 금융 및 경제 분야에서 학술 연구를 수행하면서 수년간 일했습니다. 다시 여기에는 프로그램 작성이 포함되었으며, 다시 비공식적으로 테스트하고 정확성에 대해 추론하기 위해 내 기술을 사용했습니다.. 

비록 모든 케이스를 테스트하는 것이 불가능하다는 점에서 테스트가 항상 불완전 할 것이라는 사실에 대해 감사 했음에도 불구하고 말할 수 있습니다. 엄격한 방식으로 비공식적으로 테스트 할 때 수학적 사고 방식이 꽤 좋다고 합리적으로 확신했습니다. 그렇기 때문에 나는 테스트와 정확성 증명의 차이, 그리고 그 결과에 대해 완전히 이해하지 못했습니다! ConsenSys에 입사하기 전의 경력 동안 나는 테스트를 통해 내가 생각한 것이 정확하다고 생각하는 비공식적 기술에 의존하는 것에 만족했습니다.. 

따라서 이전에 공식적인 방법을 발견하지 못했다는 사실에 다소 놀랐 기 때문에 제 배경은 이야기의 일부입니다. 나는 내가 수학 자라고 생각한다. 저는 수학, 알고리즘 및 논리를 좋아합니다. 이제는 불완전한 테스트에만 의존하는 것이 미친 것처럼 보이지만, 컴퓨터 프로그램이 제공하는 여러 가지 방법을 고려할 때 공식적인 방법이 제공 할 수있는 것과 버그를 놓칠 수있는 잠재적 인 결과에 대해 최소한 이해하지 못하는 프로그램을하는 사람에게는 미친 것처럼 보입니다. 우리 삶에 통합되었습니다. 공식적인 방법을 사용하면 테스트를 넘어서 프로그램이 사전 및 사후 조건을 포함하는 사양에 대해 올바른지 증명할 수 있습니다.. 

첫 번째 Dafny 예

간단한 예로서 음이 아닌 피제수 n을 양의 제수 d로 정수 나누기를 고려하십시오. 


n / d

아래에 표시 :

형식화 된 프로그래밍 언어에서는 입력 매개 변수를 다소 제한 할 수 있지만 항상 충분하지는 않습니다. 이 예에서 n과 d를 자연수로 지정하면 두 입력 모두 음수가 아닌 정수 여야하지만 d를 양의 정수로 제한하지는 않습니다. require 문을 통한 전제 조건의 사용은 이러한 제한을 제공하며이 메서드는 다음 경우에만 호출 될 수 있음을 의미합니다. > 0. 따라서 프로그램의 다른 부분으로 인해 이러한 전제 조건이 충족되지 않고 div가 호출되면 프로그램은 확인하지 않습니다. 그런 다음 ensures 문은 사후 조건을 제공하고 메서드 출력이 충족해야하는 사항에 대한 공식 사양을 제공합니다..

이 예제는 Dafny :“기능적 정확성을위한 언어 및 프로그램 검증 자”를 사용하여 작성되었으며 다음 요점, 즉 제가 Dafny를 좋아하는 이유입니다. 나는 많은 프로그래머들에게 프로그램의 정확성을 검증하기 위해 “공식적인 방법”을 사용한다는 생각이 다소 무섭고 종종 “너무”어렵다고 인식된다고 말하는 것이 공정하다고 생각합니다. 이것이 기술에 대한 노출 부족, 이점에 대한 이해 부족 또는이 분야의 교육 부족 때문인지 여부 이유가 무엇이든 Dafny는 모든 프로그래머가 작업에 공식적인 방법을 적용하여 신속하게 성공할 수있는 능력이 있다고 생각합니다. 위의 코드 스 니펫을 보면 프로그래밍 지식이있는 사람이라면 누구나이 Dafny 코드를 읽을 수있을 것입니다. Dafny는 프로그래머 친화적 인 언어입니다. Dafny를 조금 배우면 실험을 시작하고 기본적으로 진행하면서 배우는 것이 매우 쉽습니다. Dafny를 배우는 데 관심이 있다면 시작하기 좋은 곳은 튜토리얼 시리즈 Microsoft에 의해. 이 사이트에는 온라인 편집기도 포함되어 있으므로 자습서 예제를 사용해 보는 것은 매우 쉽습니다. 그만큼 인증 코너 YouTube 채널 유용한 참고 자료의 또 다른 출처입니다..

나의 깨달음 순간

마침내 나는 Dafny를 배우던 시절의 깨달음을 공유하고 싶었습니다. 나는 확실히 유명한 대기업으로부터 짧고 단순한 코드 조각에 대한 이야기를 들었습니다. 버그를 놓치고 궁극적으로 수백만 달러가 들었습니다. 하지만 단순한 함수에서 실수로 버그를 만드는 것이 얼마나 쉬운 지 스스로 깨닫는 경우에만 모든 것이 합리적이라고 생각합니다! 스스로에게“오, 실수하기 쉽 겠군!”이라고 말하는 순간

나의 순간은 검증 코너 동영상

이 튜토리얼에서 Rustan Leino는 두 개의 정수 x와 y를 취하고 각각 sum과 max, s와 m을 반환하는 SumMax 메서드를 거칩니다. 이 예제는 비교적 간단하며 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<= m && 와이 <= m) 보유 할 수 없습니다. 더 자세히 살펴보면이 포스트 조건이 x <= m 및 y <= m. 음, 우리는 x를 m과 같게 설정함에 따라 x가 m보다 작거나 같다는 것을 알고 있습니다. 따라서 이것은 y가 <= m 부분이 확인되지 않습니다. 어떻게 이런 일이 일어날 수 있습니까? 우리의 대수는 y : = s – m이라고 알려줍니다. s가 5이고 m이 3이고 y = 5 – 3 = 2라고 가정 해 보겠습니다. <= m; 그러나 s가 5이고 m이 1 인이 메서드를 호출한다고 가정 해 봅시다.이 입력 매개 변수를 사용하여 메서드를 호출하는 것을 막을 수는 없지만 이렇게하면 y = 5 – 1 = 4, y와 같은 문제가 발생합니다. > 미디엄. 기본적으로 여기에서 볼 수있는 것은 입력 매개 변수가 합계를 생성하는 최대 2 개의 정수를 의미하더라도 유효하지 않은 입력으로 메서드를 호출하려는 시도를 막을 수있는 것이 없다는 것입니다. s와 m의 입력을 유효한 정수로 제한하는 전제 조건이 포함되어 있지 않으면 출력 x와 y가 사양을 충족하는 결과를 낳을 수 있습니다. 우리의 방법은 잘못된 결과를 생성 할 수 있습니다. 유효한 입력을 제공하려면 s와 m 사이에 어떤 관계가 필요합니까? 더 많은 대수는 우리에게 <= m * 2는 x와 y의 유효한 해가 있어야합니다. 이것을 전제 조건으로 추가하면 Dafny는 이제 아래와 같이 코드를 확인할 수 있습니다.. 

스크린 샷 2020 12 15 at 6 46 32 pm 1 스크린 샷 2020 12 16 at 5 37 39 pm

코드에 버그를 도입하는 것이 얼마나 쉬운 지 알 수있는 예였습니다. 입력 매개 변수 ‘s’를 합계로, ‘m’을 최대 값으로 호출한다고해서 메서드가 적절하게 호출된다는 의미는 아니며 일부 더 큰 프로그램의 일부처럼 이로 인해 의도하지 않은 결과가 많이 발생할 수 있습니다. 버그 유형. Dafny 또는 공식적인 방법에 대해 더 일반적으로 배우는 다른 사람에게 유용하기를 바랍니다..

내가 지금하고있는 것

글의 끝으로 이동합니다. 내가 현재 Dafny와 함께 작업하고있는 것을보고 싶다면 이것을 확인하십시오. GitHub 저장소. R 내 자동 검증 팀의 일원입니다.&ConsenSys의 D와 우리는 Ethereum 2 Phase 0 사양의 공식 검증에 Dafny를 사용하고 있습니다. 블록 체인 공간에서 공식적인 방법을 사용하는 것은 ConsenSys가 채택한 흥미 진진한 새로운 연구 영역입니다. 저는 Eth 2.0에 대해 더 많이 배우고 자하는 모든 사람들이 우리 프로젝트 저장소에서 사용할 수있는 리소스를 살펴볼 것을 권장합니다..

뉴스 레터 최신 이더 리움 뉴스, 엔터프라이즈 솔루션, 개발자 리소스 등을 보려면 뉴스 레터를 구독하십시오.

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