열쇠

이 문서에는 여러 가지 문제가 있습니다.개선을 돕거나 토크 페이지에서 이러한 문제에 대해 논의해 주십시오.(이러한 템플릿메시지를 삭제하는 방법과 타이밍에 대해 설명합니다) 이 문서에는 일반적인 참조 목록이 포함되어 있지만 대응하는 충분한 인라인 인용이 없습니다. 좀 더 정밀한 인용문을 도입하여 개선해 주시기 바랍니다. (2016년 8월) (템플릿 메시지 삭제 방법 및 시기 확인) 이 기사는 대부분의 독자들이 이해하기에는 너무 전문적일 수 있다. 기술적인 세부사항을 삭제하지 않고 비전문가도 쉽게 이해할 수 있도록 개선해 주시기 바랍니다. (2019년 3월) (이 템플릿 메시지 삭제 방법 및 삭제 시기 확인) (이 템플릿메시지를 삭제하는 방법과 타이밍을 확인합니다)

열쇠

KeY 1.4 스크린샷
개발자	칼스루에 공과대학 칼스루에 공과대학 칼스루에 공과대학, 다름슈타트
안정된 릴리스	2.8.0 / 2020년 12월 18일 (2020-12-18)[1]
기입처	자바
운영 체제	Linux, Mac, Windows, Solaris
이용가능기간:	영어
유형	정식 검증
면허증.	GPL
웹 사이트	www.key-project.org

KeY 도구는 Java 프로그램의 정식 검증에 사용됩니다.Java 모델링 언어로 작성된 사양을 Java 소스 파일에 사용할 수 있습니다.이것들은 동적 로직의 이론으로 변환되어 동적 로직의 관점에서 동일하게 정의된 프로그램 의미론과 비교됩니다.KeY는 대화형(즉, 손으로)과 완전 자동화된 정확성 증명을 모두 지원한다는 점에서 상당히 강력하다.실패한 증명 시도는 보다 효율적인 디버깅 또는 검증 기반 테스트에 사용할 수 있습니다.C 프로그램 또는 하이브리드 시스템의 검증에 KeY를 적용하기 위해 몇 가지 확장이 있었다.KeY는 독일 Karlsruhe Institute of Technology에 의해 공동 개발되었습니다.독일 테크니스테트 다름슈타트 대학교와 스웨덴 예테보리에 있는 Chalmers 공과 대학교는 GPL에 따라 면허를 취득했습니다.

개요

KeY에 대한 일반적인 사용자 입력은 JML에 주석이 있는 Java 소스 파일로 구성됩니다. 둘 다 KeY의 내부 표현인 동적 로직으로 변환됩니다.주어진 명세서에서 몇 가지 입증 의무가 발생하며, 이는 곧 증거를 찾아야 한다는 것이다.이를 위해 프로그램은 소위 업데이트에 저장된 프로그램 변수에 대한 변경으로 상징적으로 실행됩니다.프로그램이 완전히 처리되면 1차 논리 증명 의무가 남습니다.KeY 시스템의 중심에는 증명을 닫는 데 사용되는 시퀀셜 미적분에 기초한 1차 정리 검증기가 있습니다.간섭규칙은 시퀀스에 대한 변경을 설명하기 위한 자체 간단한 언어로 구성된 이른바 태클릿으로 캡처됩니다.

자바 카드 DL

KeY의 이론적 기반은 Java Card DL이라고 불리는 형식 논리입니다. DL은 Dynamic Logic의 약자입니다.Java Card 프로그램에 맞춘 1차 동적 로직 버전입니다.예를 들어 ${\displaystyle \to }$ [${\displaystyle \alpha }$] ${\$ { $displaystyle \phi \rightarrow$[ \$alpha ]\psi$와 같은 문(문)을 사용할 수 있습니다.이 문$(문$)은 Java$$ Card $(\displaystyle \alpha)$를 실행함으로써 도달 가능한 모든 프로그램 상태에서 조건(\displaystyle \$psi)$을 직감적으로 유지할 수 있습니다.사전 $조건{\displaystyle }$ ${\$ { $displaystyle \$$phi$$$$}$ ${\$ {\ {\ {\ $pre$ { { { { { { ${\displaystyle \{}$ { { ${$ display display $display{\displaystyle }$ display $display$ display display $display$ ${\displaystyle \mathrm{display}}$ ${\displaystyle \mathrm{display}}$ { \$phi \ }${ ${\displaystyle \{}$ { { { { { { { { { pre$$ pre pre pre pre pre pre pre pre pre pre pre ${\displaystyle \mathrm{pre}}$ { pre pre pre pre pre pre pre pre pre pre pre$$ pre그러나 동적 로직은 공식에 [$]$ {$displaystyle$[\$alpha$과${\displaystyle }$같은 중첩된 프로그램 양식이 포함될 수 있거나 양식이 포함된 공식에 대한 정량화가 가능하다는 점에서 Hoare 로직을 확장합니다.종료를 포함한 이중 모달리티${\displaystyle \alpha }$ ${\$ （ \ $displaystyle$\ $langle \ alpha$ \ $rangle$）도$$ 있습니다.이 다이내믹 로직은 (모달리티의 수가 무제한인) 특수한 멀티모달 로직으로 볼 수 있습니다.각 Java $블록\alpha$에는 $[$$](\displaystyle [\alpha$])와${\displaystyle }$[$](\displaystyle \langle \ala$가 있습니다.

Deduction component

At the heart of the KeY system lies a first-order theorem prover based on a sequent calculus. A sequent is of the form ${\displaystyle \Gamma \vdash \Delta }$ where ${\displaystyle \Gamma }$ (assumptions) and ${\displaystyle \Delta }$ (propositions) are sets of formulas with the intuitive meaning that ${\displaystyle \bigwedge _{\gamma \in \Gamma }\gamma \rightarrow \bigvee _{\delta \in \Delta }\delta }$ holds true. By means of deduction, an initial sequent representing the proof obligation is shown to be constructible from just fundamental first-order axioms (such as equality ${\displaystyle e\ {\dot {=}}\ e}$).

Symbolic execution of Java code

During that, program modalities are eliminated by symbolic execution. For instance, the formula ${\displaystyle x\ {\dot {=}}\ 0\rightarrow [x++;]x\ {\dot {=}}\ 1}$ is logically equivalent to ${\displaystyle x\ {\dot {=}}\ 0\rightarrow x\ {\dot {=}}\ 0}$. As this example shows, symbolic execution in dynamic logic is very similar to calculating weakest preconditions. Both ${\displaystyle [\alpha ]\psi }$ and ${\displaystyle wp(\alpha ,\psi )}$ essentially denote the same thing – with two exceptions: Firstly, ${\displaystyle wp}$ is a function of some meta-calculus while ${\displaystyle [\alpha ]\psi }$ really is a formula of the given calculus. Secondly, symbolic execution runs through the program forward just as an actual execution would. To save intermediate results of assignments, KeY introduces a concept called updates, which are similar to substitutions but are only applied once the program modality has been fully eliminated. Syntactically, updates are consist of parallel (side-effect free) assignments written in curly braces in front of a modality. An example of symbolic execution with updates: ${\displaystyle [x=3;x=x+1;]x\ {\dot {=}}\ 4}$ is transformed to ${\displaystyle \{x:=3\}[x=x+1;]x\ {\dot {=}}\ 4}$ in the first step and to ${\displaystyle \{x:=4\}[]x\ {\dot {=}}\ 4}$ in the second step. The modality then is empty and "backwards application" of the update to the postcondition yields a precondition where ${\displaystyle x}$ could take any value.

예

다음 방법이 음이 아닌 $정수{\displaystyle }$x(\$displaystyle$ x$)$와 y$(\displaystyle$ y$)$의 곱을 계산한다고 가정합니다.

인트 후우 (인트 x, 인트 y) {     인트 z = 0;     하는 동안에 (y > 0)         한다면 (y % 2 == 0) {             x = x*2;             y = y/2;         } 또 다른 {             y = y/2;             z = z+x;             x = x*2;         }     돌아가다 z; } 

$따라서{\displaystyle }$ x${\displaystyle 0}$ 0$0$ 0 y${\displaystyle 0}$0 \ $displaystyle$x \$geq 0$\ $land$ y \$$geq$$ 0 e 0 , the $the{\displaystyle }$ the $=$ x${\displaystyle e}$ y$$\ $displaystyle$ z \ { =} \$x$ \ $cdot$y $\}$ eeee,e,,e ,eeeeeee,,eeee,eeee,eeeee,,,eeeeeeeeeeeeeeeeeee,eeeee,e,,e,,,ee,ee오른쪽 그림에서 확인할 수 있습니다.

결과 증명 트리

기타 기능

심볼릭 실행 디버거

Symbolic Execution Debugger는 프로그램의 제어 흐름을 프로그램을 통해 특정 지점까지 실행 가능한 모든 실행 경로를 포함하는 심볼릭 실행 트리로 시각화합니다.이클립스 개발 플랫폼의 플러그인으로 제공됩니다.

테스트 케이스 생성기

KeY는 Java 프로그램의 유닛 테스트를 생성할 수 있는 모델 기반 테스트 도구로 사용할 수 있습니다.테스트 데이터와 테스트 케이스를 도출한 모델은 정식 사양(JML에 제공)과 KeY 시스템에 의해 계산되는 테스트 대상 구현의 상징 실행 트리로 구성된다.

KeY 시스템의 분포와 변종

KeY는 Java로 작성되어 GPL로 라이선스가 부여된 무료 소프트웨어입니다.프로젝트 웹사이트에서 다운로드 할 수 있습니다.현재 미리 컴파일된 바이너리는 없습니다.KeY는 컴파일 및 설치 없이 Java Web Start를 통해 직접 실행할 수 있습니다.

케이호아레

KeY-Hoare는 KeY 위에 구축되어 있으며, 상태 업데이트를 포함한 Hoare 미적분을 특징으로 합니다.상태 업데이트는 Kripke 구조에서 상태 천이를 설명하는 수단입니다.이 미적분은 KeY의 주요 분기에서 사용되는 미적분의 하위 집합으로 볼 수 있습니다.Hoare 미적분의 단순성으로 인해, 이 구현은 본질적으로 학부 수업에서 공식적인 방법을 예시하는 것을 의미합니다.

KeYmaera/KeYmaeraX

KeYmaera [1](이전의 HyKeY)는 미분 동적 논리 dL[2]에 대한 미적분을 기반으로 하는 하이브리드 시스템을 위한 연역적 검증 도구이다.KeY 도구를 Mathematica와 같은 컴퓨터 대수 시스템과 대응하는 알고리즘 및 증명 전략으로 확장하여 하이브리드 시스템의 실제 검증에 사용할 수 있도록 합니다.

KeYmaera는 Oldenburg 대학과 Carnegie Mellon 대학에서 개발되었습니다.그 도구의 이름은 고대 그리스 신화에 나오는 잡종 동물 키메라와의 동음이의어로 선택되었다.

카네기 멜론 대학에서 개발한 KeYmaeraX[3]는 KeYmaera의 후속 제품이다.그것은 완전히 다시 쓰여졌다.

C의 KeY

C용 KeY는 C 프로그래밍 언어의 서브셋인 MISRA C에 KeY 시스템을 적용한 것입니다.이 변형은 더 이상 지원되지 않습니다.

ASMKEY

ETH 취리히에서 개발한 추상 스테이트 머신의 심볼릭 실행을 위해 KeY를 사용하기 위한 적응도 있습니다.이 변형은 더 이상 지원되지 않습니다.

레퍼런스

원천

• 객체 지향 소프트웨어 검증: KeY 어프로치베른하르트 베커트, 라이너 헤른레, 피터 H. 슈미트(에드)Springer, 2007년ISBN 978-3-540-68977-5.
• 소프트웨어 연역 검증– KeY 북: 이론에서 실천으로.볼프강 아렌트, 베른하르트 베커트, 리처드 부벨, 라이너 헤른레, 피터 H. 슈미트, 마티아스 울브리치(에드).스프링거, 2016년ISBN 978-3-319-49812-6
• 정식 소프트웨어 검증 교육을 위한 도구 비교.잉고 파이너러와 거노트 살저.Springer, 2008
• 증거를 사용한 프로그래밍: 완전히 올바른 소프트웨어를 위한 언어 기반 접근법.애런 스텀프.확인된 소프트웨어:이론, 도구, 실험, 2005.
• 높은 보증(보안 또는 안전) 및 Free-Libre/Open Source Software(FLOSS)를 제공합니다.David Wheeler, 2009

외부 링크

Wikimedia Commons에는 KeY 프로그램 검증 도구와 관련된 미디어가 있습니다.

• KeY 프로젝트 홈페이지
• KeYmaera 홈페이지
• KeYmaeraX 홈페이지