분리논리

컴퓨터 공학에서 분리^[1] 논리는 프로그램에 대한 추론 방법인 Hoare 논리의 확장입니다.그것은 존 C에 의해 개발되었다. 레이놀즈, 피터 오힌, 사민 이스티아크, ^[1]^[2]^[3]^[4]양홍석 등 로드 버스톨의 ^[5]초기 작품을 바탕으로 한 작품입니다.분리 로직의 어설션 언어는 번치된 의미(^[6]BI) 로직의 특수한 경우입니다.O'Hearn의 CACM 리뷰 기사는 2019년 ^[7]초까지 이 주제에 대한 개발을 도표화한다.

개요

분리 로직은 다음 사항에 대한 추론을 용이하게 합니다.

포인터 데이터 구조를 조작하는 프로그램 - 포인터 존재에 숨겨진 정보를 포함한다.
"소유권 이전"(의미적 틀 공리) 및
동시 모듈 간의 가상 분리(추론)

분리 로직은 피터 오힌과 다른 사람들에 의해 국지적 추론으로 기술된 개발 연구 분야를 지원하며, 프로그램 구성요소의 사양과 증명은 시스템의 전체 전역 상태가 아닌 구성요소에 의해 사용되는 메모리의 일부만을 언급합니다.애플리케이션에는 자동 프로그램 검증(알고리즘이 다른 알고리즘의 유효성을 검사하는 경우)과 소프트웨어의 자동 병렬화가 포함됩니다.

아사션: 연산자와 의미론

분리 로직 어설션은 스토어와 힙으로 구성된 "상태"를 기술하며, 로컬(또는 스택 할당) 변수와 C 및 Java와 같은 공통 프로그래밍 언어의 동적으로 할당된 객체의 상태와 대략 일치합니다. $저장소는$ 에 값을 매핑하는 함수입니다 $.$ $히프$ h(\ $displaystyle$ h $)$ 는 $h$ 메모리 주소를 값에 매핑하는 부분 함수입니다.두 $h$ 의 humph(\ $displaystyle$ h $)$ 및 $h$ $h'$ $(\$ $displaystyle$ h $h\,\bot \,h'$ 도메인이 겹치지 않으면( $h\,\bot \,h'$ , $h(\ell )$ 메모리주소에 대해 $\ell$ $\ell$ $(\displaystyle$ $\ell$ h $(\displaystyle$ $\ell$ h $)$ 및 $h'(\ell )$ displaystyle h $h(\ell )$ ) 중 $h(\ell )$ 이상 $h'(\ell )$ 는 분리됩니다(\ $displaystyle$ $h\,\bot \,h'$ $(\displaystyle$ $h'(\ell )$ $)$ $h'(\ell )$ 정의되어 있지 않습니다).

이 로직에서는 s $s,h\models P$ $p$ P (\ $displaystyle$ s $,$ $h\models$ P $s,h\models P$ ) $s,h\models P$ 의 판단을 증명할 수 있습니다. $s$ 서 $s$ 는 스토어, $\displaystyle$ h는 $h$ 힙, $\displaystyle$ P는 $P$ 지정된 스토어 및 힙에 대한 어설션입니다.분리 로직 어설션( $P$ {\ $displaystyle$ P $},$ $Q$ {\ $displaystyle$ Q $Q$ $P\ast Q$ ${\$ $displaystyle$ R $R$ 로 표시됨)에는 표준 부울 접속사 및 $\mathbf {e} \mathbf {m} \mathbf {p}$ $e\mapsto e'$ $\mathbf {e} \mathbf {m} \mathbf {p}$ \ $mathbf$ $\mathbf {e} \mathbf {m} \mathbf {p}$ { $m$ $}$ \ $mathbf {p$ $e-map이 포함$ 됩니다 $P\ast Q$ $P{-\!\!\ast }\,Q$ $\ast },Q$ 。 $e$ 서e(\ $displaystyle$ e) 및 $(\$ e $')$ 는 $e'$ 표현입니다.

$\mathbf {e} \mathbf {m} \mathbf {p}$ em p $\mathbf {e} \mathbf {m} \mathbf {p}$ {\ $displaystyle$ \ $mathbf {e}$ \ $mathbf {p}$ \ $mathbf$ {p}는 $\mathbf {e} \mathbf {m} \mathbf {p}$ $s,h\models \mathbf {e} \mathbf {m} \mathbf {p}$ $h$ 모든 $s,h\models \mathbf {e} \mathbf {m} \mathbf {p}$ 에 $대해$ 정의되지 않은 $경우$ $s,h\models \mathbf {e} \mathbf {m} \mathbf {p}$ 힙이 비어 있음을 $나타냅니다$ 즉, $s,h\models \mathbf {e} \mathbf {m} \mathbf {p}$ , $h$ † $s,h\models \mathbf {e} \mathbf {m} \mathbf {p}$ displaystyle s , h \ $models$ \ $mathbf$ { $e }$ \ $mathbf {p }$ $。$
이진 연산자 $"\displaystyle \mapsto"$ 는 $\mapsto$ 주소와 값을 가져와서 히프가 정확히1개의 로케이션으로 정의되어 있으며 지정된 주소에 지정된 값을 매핑합니다. $h([\![e]\!]_{s})=[\![e']\!]_{s}$ $s,h\models e\mapsto e'$ ( [ $e$ $h([\![e]\!]_{s})=[\![e']\!]_{s}$ ) $h([\![e]\!]_{s})=[\![e']\!]_{s}$ [ [ $h([\![e]\!]_{s})=[\![e']\!]_{s}$ s \ $displaystyle$ $h$ ( [ \ ! [ $e$ ]\ ![ $h([\![e]\!]_{s})=[\![e']\!]_{s}$ ]\ ]s \ $displaystyle$ h ( [ \ ! [ e ]\ ![ e $]\ s$ [ e` \ $]\$ $mapsto$ e $'$ ） $_{s$ $[\![e]\!]_{s}$ 서 $[\![e]\!]_{s}$ [ $[\![e]\!]_{s}$ s $\$ _ ${s}}$ 은 $[\![e]\!]_{{s}}$ (는) $store$ s {\ $displaystyle$ s $s$ 에서 평가된 식 $e$ {\ $displaystyle$ e $}$ 의 $e$ 값을 나타냅니다. $h$ {\ $displaystyle$ h}는 $h$ 정의되어 있지 않습니다.
이진 연산자 ${\(별$ 또는 분리 접속사로 발음됨 $)$ 는 각각 두 개의 인수가 유지되는 두 개의 분리된 부분으로 힙을 분할할 수 있다고 주장합니다. $h_{1}\,\bot \,h_{2}$ $s,h\models P\ast Q$ $s,h\models P\ast Q$ , h $s,h\models P\ast Q$ $h_{1},h_{2}$ P $s,h\models P\ast Q$ $h_{1},h_{2}$ Q ( h 1, $h$ $h_{1},h_{2}$ $2$ { $display$ $style$ $h_{1$ } , $h_{2}$ )가 $h_1, h_2$ $h_{1}\,\bot \,h_{2}$ $h_{1}\,\bot \,h_{2}$ 하는 $s,h\models P\ast Q$ 경우 $s,h\models P\ast Q$ h 1 $h_{1},h_{2}$ $h_{1}\,\bot \,h_{2}$ $h_{1}\,\bot \,h_{2}$ 2 $h_{1}\,\bot \,h_{2}$ \ $display$ style $h_{1}$ , \ $bot$ \ h 、 $h$ $h=h_{1}\cup h_{2}$ $h=h_{1}\cup h_{2}$ 1 $h=h_{1}\cup h_{2}$ $h=h_{1}\cup h_{2}$ _ { 1 \ display $style$ h $h=h_{1}\cup h_{2}$ { $h_{1}\,\bot \,h_{2}$ 1 ） = $h=h_{1}\cup h_{2}$ h $h=h_{1}\cup h_{2}$ _ $h=h_{1}\cup h_{2}$ 1 、 h _ { 1 （ h ）） $h=h_{1}\cup h_{2}$ 。 $s,h_{2}\models Q$ 2 $(\displaystyle$ s $,h_{2}\models$ Q $s,h_{2}\models Q$
이진 연산자 - ${\$ {\ $displaystyle -\\!$ \ $ast }($ 매직봉 또는 분리 암시로 발음됨)은 첫 번째 인수를 충족하는 분리된 부분으로 힙을 확장하면 두 번째 인수를 충족하는 힙이 생성된다고 주장합니다 $.$ 예를 들어 $s,h\models P-\!\!\ast \,Q$ $s,h\models P-\!\!\ast \,Q$ , $s,h\models P-\!\!\ast \,Q$ - $s,h\models P-\!\!\ast \,Q$ P - ${\$ $s,h\models P-\!\!\ast \,Q$ ( \ $display style s$ , h \ $models$ P - $s,h\models P-\!\!\ast \,Q$ \ \ ! ) $\$ $ast ",$ $s,h'\models P$ $"$ (각 $s,h\models P-\!\!\ast \,Q$ $h'\,\bot \,h$ $h'\,\bot \,h$ \ $displaystyle$ h \ $displaystyle$ h , \ bot $s,h'\models P$ " $, h$ $s,h'\models P$ 에 $h'\,\bot \,h$ $s,h\cup h'\models Q$ $s,h'\models P$ s $s,h\cup h'\models Q$ , $s,h\cup h'\models Q$ " h " $s,h\cup h'\models Q$ " $s,h\cup h'\models Q$ " " $s,h\cup h'\models Q$ " " " " " " " h " h " s , $h$ " \ $displaystyle$ s $, h$ " \ $models$ Q $"$ 가 $s,h\cup h'\models Q$ 유지되도록 $s,h'\models P$ .

연산자 $"\displaystyle \ast"$ $-\!\!\ast$ 및 $\ast$ $"\displaystyle -\!"$ \ $ast }$ 은 $-\!\!\ast$ $($ 는) 기존의 접속 연산자 및 시사 연산자와 몇 가지 속성을 공유합니다.모더스 포넨과 유사한 추론 규칙을 사용하여 결합할 수 있습니다.

&quot;디스플레이 스타일&quot;\frac {s,h\models P\ast (P-\\\!&quot;\ast \,Q)}{s,h\models Q}}

$s,h\cup h'\models P\ast Q\Rightarrow R$ $s,h\models P\Rightarrow Q-\!\!\ast \,R$ $,$ $s,h\cup h'\models P\ast Q\Rightarrow R$ $,$ p $s,h\cup h'\models P\ast Q\Rightarrow R$ $s,h\cup h'\models P\ast Q\Rightarrow R$ $,$ $h, h\cup h'\models$ $P\rightarrow$ R $,$ $s,h\models P\Rightarrow Q-\!\!\ast \,R$ , h, h, rightarrow, h, $right$ , r, h, h, h, $right$ , r $,$ h, r, h, h, h, h, $s,h\models P\Rightarrow Q-\!\!\ast \,R$ r, $right$ , r, r, r, r, r, r, r, r, r, r, r, r, r, r, r, r, r, r, r, r, r, r, r, r, r, r, r, r, r, r, r, r, r $h\,\bot \,h'$ h ${\$ $s,h\models P\Rightarrow Q-\!\!\ast \,R$ \ $displaystyle$ h , \ $bot$ " , $h$ " $h\,\bot \,h'$ 。 보다 정확하게는 인접 연산자는 _ $\_\ast Q$ Q $\_\ast Q$ \ $displaystyle \$ \ \ $ast$ Q } $Q-\!\!\ast \,\_$ Q - $Q-\!\!\ast \,\_$ _ $Q-\!\!\ast \,\_$ $displaystyle$ Q - $Q-\!\!\ast \,\_$ \ \ \ \ \ ! $\ast \,\_$

프로그램에 대한 추론: 3중 및 증명 규칙

분리 논리에서는 호어 3배는 호어 논리와는 약간 다른 의미를 가집니다.트리플 $\{P\}\ C\ \{Q\}$ { $\{P\}\ C\ \{Q\}$ $\{P\}\ C\ \{Q\}$ { $\{P\}\ C\ \{Q\}$ $}$ { { $displaystyle$ \ { P \ } \ $C \$ { { Q $\{P\}\ C\ \{Q\}$ \ } ,,、 C { $displaystyle$ C $C$ } $C$ 이 $전제조건$ P { $displaystyle$ P }를 $\{P\}\ C\ \{Q\}$ $P$ 만족하는 초기상태에서 실행되면 프로그램이 잘못되지 않으며(예를 들어 정의되지 않은 동작이 있는 경우) 종료된 경우 최종 후 상태가 충족됩니다. $Q$ 으로C $(\$ $displaystyle$ Q $Q$ C(\ $displaystyle$ C $)$ 는 $C$ $실행$ 중에 전제조건에서 존재한다고 주장되거나 C $(\displaystyle$ C $)$ 가 $C$ 할당한 메모리 위치에만 액세스할 수 있습니다.

분리 로직은 Hoare 로직의 표준 규칙 외에 다음과 같은 매우 중요한 규칙을 지원합니다.

${{P\}\{Q\}{P\ast R\}\C\{Q\ast R\}}~{\mathsf {mod}}(C)\cap {mathsf {fv}(R)=emptyset$

이는 프레임 규칙(프레임 문제에서 따온 이름)이라고 불리며 로컬 추론을 활성화합니다.작은 상태( $P$ 하는 P $\displaystyle$ P $)$ 에서 안전하게 실행되는 프로그램은 더 큰 상태( $P\ast R$ 하는 P $\displaystyle$ P $\ast$ R $P\ast R$ 에서도 $R$ 실행될 수 있으며, 그 실행은 상태 추가 부분에 영향을 미치지 않으며( $따라서$ R $\displaystyle$ R $)$ 사후 조건에서도 true로 유지됩니다.사이드 조건에서는C에 $의해$ 수정된 변수 중 어느 것도R {\ $displaystyle$ R $R$ 에서 $C$ 빈 변수가 발생하지 않도록 지정함으로써 이를 적용합니다 $.$ 즉, R {\ $displaystyle$ R $R$ 의 f v {\ $displaystyle$ { $}}$ 집합 ${\mathsf {fv}}$ {\displaystyle}에 있는 변수는 없습니다.

공유.

분리 로직은 단순히 분리 결합을 사용하여 설명할 수 있는 규칙적인 공유 패턴을 나타내는 데이터 구조에 대한 포인터 조작의 간단한 증거로 이어집니다. 예로는 단일 및 이중으로 연결된 목록과 다양한 트리가 있습니다.그래프, DAG 및 더 일반적인 공유가 있는 기타 데이터 구조는 공식 및 비공식 증거 모두에서 더 어렵다.그럼에도 불구하고, 분리 논리는 일반적인 공유가 있는 프로그램에 대한 추론에 성공적으로 적용되었다.

O'Hearn과 Ishtiaq는 POPL'01 ^[3]논문에서 마법 지팡이가 어떻게 ${-\!\!*}$ 결합하는지를 설명했습니다. $©$ {\ $displaystyle {-\$ ! $\!*}}:$ 적어도 ${-\!\!*}$ 원칙적으로는 공유가 존재하는 상태에서 추론할 수 있습니다.예를 들어, 트리플에서

$\displaystyle \{(x\mapsto -)\ast(x\mapsto 42){-\!\!*}P)\}\[x]=42\{P\}$

x $(\displaystyle$ x $x$ $x$ 에서 힙을 변형시키는 문장의 가장 약한 전제조건을 얻었으며, 이는 분리 결합사를 사용하여 깔끔하게 배치되는 조건뿐만 아니라 모든 후조건에 적용됩니다.이 아이디어는 Yang에 의해 훨씬 더 발전되었습니다 $.$ Yang은 ${-\!\!*}$ $displaystyle {-\!$ $\!*}:$ 전형적인 ${-\!\!*}$ 쇼르-웨이트 그래프 표시 ^[8]알고리즘의 돌연변이에 대한 국소적 추론을 제공한다.마지막으로, 이 방향의 가장 최근의 작품 중 하나는 호보(Hobor)와 빌라드(^[9]Villard)의 작품입니다. 호보(Villard)는 $"*$ 만을 고용하지 않습니다. $\!*}:$ 접속형 ${-\!\!*}$ $"\"\displaystyle$ \ $cup\!"\!$ $\!\!*}$ 는 중복접속사 $\cup \,\!\!\!\!\!*$ 또는 sepish로 ^[10]불리며 중복되는 데이터 구조를 설명하는 데 사용할 수 있습니다. $P\cup \!\!\!\!\!*Q$ $P\cup \!\!\!\!\!*Q$ $P\cup \!\!\!\!\!*Q$ $P\cup \!\!\!\!\!*Q$ 、 \ $style$ P \ $cup$ \ ! \ \ \ \ \ \ $P\cup \!\!\!\!\!*Q$ 。 $\!\!*Q는$ 하위 $h_{P}$ $h_{P}$ P $(\$ 및 $h_{Q}$ (\ $displaystyle$ ${$ Q $h$ 에 대해 P $(\$ $displaystyle$ h_{ $h_{Q}$ $})$ 와 Q(\displaystyle h_ $h_{P}$ $h_{Q}$ {Q})가 $Q$ 유지되는 $경우$ H $(\$ $displaystyle$ H $)$ 의 $h_{P}\cap h_{Q}$ 가 $h$ 비어 있지 않을 수 있습니다 $h_{P}\cap h_{Q}$ $\cap h_{Q}:$ 공통 $h_{P}\cap h_{Q}$ . $P\cup \!\!\!\!\!*Q$ 으로 P $P\cup \!\!\!\!\!*Q$ Q $P\cup \!\!\!\!\!*Q$ \ $displaystyle$ P \ $cup$ \ $P\cup \!\!\!\!\!*Q$ ! $\!\!\!*Q}$ 는 $P\cup \!\!\!\!\!*Q$ 관련 로직의 퓨전 연결 버전이라고 볼 수 있습니다.

동시 분리 논리

동시 프로그램의 분리 로직 버전인 CSL(Concurrent Separation Logic)은 증명 규칙을 사용하여 Peter O'[11]Hearn에 의해 처음 제안되었습니다.

{{P_{1}\}C_{1}\}쿼드 \{P_{2}\}C_{2}\}{{P_{1}*P_{1}C_{2}\}{Q_{2}\}{Q}

따라서 개별 스토리지에 액세스하는 스레드에 대한 독립적인 추론이 가능합니다.O'Hearn의 증명 규칙은 ^[12]동시성에 대한 추론에 대한 토니 호어의 초기 접근방식을 채택하여 분리 논리에서 추론에 의한 분리를 보장하는 범위 지정 제약의 사용을 대체했습니다.Hoare의 접근방식을 힙 할당 포인터의 존재 하에서 적용하도록 확장하는 것 외에도, O'Hearn은 동시 분리 로직에서 추론이 프로세스 간의 힙 부분의 동적 소유권 전송을 어떻게 추적할 수 있는지를 보여주었다. 이 문서의 예는 포인터 전송 버퍼와 메모리 매니저를 포함한다.

수잔 오위키와 데이비드 그리스의 간섭 자유에 관한 초기 고전적인 작업에 대해 언급하면서, O'Hearn은 그의 시스템이 암묵적인 방식으로 간섭을 배제하기 때문에 비간섭에 대한 명시적인 체크는 필요하지 않다고 말한다.

동시 분리 논리에 대한 모델은 스티븐 브룩스가 O'Hearn의 ^[13]동반 논문에서 처음 제공했습니다.논리의 건전성은 어려운 문제였고, 사실 존 레이놀즈의 반례는 발표되지 않은 이전의 논리의 불건전성을 보여주었다. 레이놀즈의 사례로 제기된 문제는 오힌의 논문에 간략하게 기술되어 있고, 브룩스의 논문에 더 철저하게 기술되어 있다.

처음에 CSL은 Dijkstra가 느슨하게 연결된 ^[14]프로세스라고 부르는 것에 매우 적합한 것으로 보였지만, 아마도 상당한 간섭을 수반하는 세분화된 동시 알고리즘에는 적합하지 않을 것입니다.그러나 논리 연결의 비표준 모델과 심지어 Hoare 3중 모델을 사용하는 경우 CSL의 기본 접근법이 처음에 예상했던 것보다 훨씬 강력하다는 것을 점차 깨닫게 되었다.

특정 힙 ^[15]모델 대신 임의의 부분 교환 모노이드에 대해 해석된 전제 조건과 사후 조건이 공식인 Hoare 3중으로 작동하는 분리 로직의 추상 버전이 제안되었다.나중에, 가환 monoid의 적절한 선택에 의해,은 놀라울 정도로가 동시 분리 논리의 추상적인 버전의 증명 규칙 이성에 참견을 하고 병행 프로세스에 대해, 예를 들어 원래 간섭에 대해 이성에 제안된 rely-guarantee 기술 인코딩에 의해;[16]이 일에 사용할 수 있는 발견되었다.e모델의 리먼트는 자원이 아니라 프로그램 상태의 "뷰"로 간주되었으며, Hoare의 비표준 해석은 사전 및 사후 조건의 비표준 판독에 수반된다.마지막으로, CSL 스타일의 원칙은 세분화된 ^[17]동시 알고리즘에 대한 추론을 위한 모듈러 기술을 제공하기 위해 프로그램 상태 대신 프로그램 이력에 대한 추론을 구성하는데 사용되어 왔다.

CSL 버전은 다음 섹션에서 설명하듯이 많은 인터랙티브 및 반자동(또는 '중간') 검증 도구에 포함되어 있습니다.특히 중요한 검증 작업은 여기에 언급된 μC/OS-II 커널입니다.그러나 단계가 ^[18]이루어졌음에도 불구하고 CSL 스타일의 추론은 자동 프로그램 분석 카테고리의 비교적 적은 도구에 포함되어 있다(다음 섹션에 언급되어 있지 않다).

O'Hearn과 Brookes는 동시 분리 ^[19]로직을 발명한 공로로 2016 Gödel Prize의 공동 수상자입니다.

검증 및 프로그램 분석 도구

프로그램에 대한 추론 도구는 사용자 입력이 필요 없는 완전 자동 프로그램 분석 도구에서 인간이 증명 프로세스에 밀접하게 관여하는 인터랙티브 도구에 이르기까지 다양한 범위에 속합니다.이러한 툴이 많이 개발되고 있습니다.다음 목록에는 각 카테고리의 담당자가 몇 명 포함되어 있습니다.

자동 프로그램 분석.이러한 도구는 일반적으로 제한된 종류의 버그(예: 메모리 안전 오류)를 찾거나 버그가 없음을 증명하려고 시도하지만 완전한 정확성을 증명하는 데는 부족합니다.
- 현재 예로는 분리 로직과 바이 ^[20]압류에 기반한 Java, C 및 Objective-C 정적 분석 도구인 Facebook User가 있습니다.2015년 현재 페이스북 모바일^[21] 앱으로 전송되기 전에 매월 수백 개의 버그가 인듀에 의해 발견되고 개발자에 의해 수정되고 있습니다.
- 그 외의 예로는 SpaceInvader(최초의 SL아나라이저 중 하나), Predator(여러 검증 경쟁에서 승리), MemCAD(쉐이프와 수치 속성을 혼합한 것), SLAyer(Microsoft Research의 디바이스 드라이버에 있는 데이터 구조에 초점을 맞춘 것) 등이 있습니다.
인터랙티브 프루프Coq 증명 보조 및 HOL(증명 보조)과 같은 인터랙티브 정리 프로버에 분리 로직의 임베딩을 사용하여 증명되었습니다.프로그램 분석 작업에 비해 이러한 툴은 인간의 노력에 더 많은 것을 요구하지만 기능적 정확성까지 더 깊은 특성을 입증합니다.
- FSCQ 파일^[22] 시스템의 증명으로, 규격에는 크래시 시의 동작과 통상의 동작이 포함됩니다.이 작품은 2015년 운영체제 원리에 관한 심포지엄에서 최우수 논문상을 수상하였습니다.
- Coq 프루프 어시스턴트의 분리 로직을 위한 Iris 프레임워크를 사용하여 RustBelt 프로젝트에서 Rust 유형 시스템의 큰 조각과 일부 표준 라이브러리를 검증합니다.
- 검증 가능한 C를 사용한 암호화 인증 ^[23]알고리즘의 OpenSSL 구현 검증
- 시판되는 OS 커널의 주요 모듈인 μC/OS-II 커널을 검증하는 것으로,^[24] 시판되는 최초의 선제 커널입니다.
- 다른 예로는 Coq 증명 도우미용^[25] Ynot 라이브러리, HOL에 Smallfoot 내장, 세분화된 동시 분리 논리 및 Bedrock(저수준 프로그래밍용 Coq 라이브러리) 등이 있습니다.
중간.많은 툴은 사용자가 함수에 대한 사전/사후 사양이나 루프 불변수 등의 어설션을 입력할 것으로 예상하기 때문에 프로그램 분석보다 더 많은 사용자 개입을 필요로 하지만, 이 입력이 주어진 후에는 완전 또는 거의 자동화를 시도합니다. 이 검증 모드는 J King의 검증과 같은 1970년대의 고전적인 작업으로 되돌아갑니다.스탠퍼드 파스칼 검증기이 스타일의 검증자는 최근에 자동 활성 검증이라고 불리며, 프로그래머와 타입 체커 사이의 상호작용과 유사한 아사트 체크 루프를 통해 검증자와 상호작용하는 방법을 환기하려는 용어입니다.
- 최초의 분리 논리 검증자인 Smallfoot은 이 중간 범주에 속했습니다.사용자가 사전/사후 사양, 루프 불변량 및 잠금 리소스 불변량을 입력해야 했습니다.그것은 프레임 공리를 추론하는 자동 방법뿐만 아니라 심볼 실행 방법을 도입했다.Smallfoot에는 동시 분리 로직이 포함되어 있습니다.
- 스몰풋RG는 분리 로직의 결합과 동시 프로그램에 대한 전형적인 의존/보증 방법의 검증자입니다.
- 힙홉은 Singularity(운영체제)의 아이디어를 따라 메시지 전달을 위한 분리 로직을 구현합니다.
- Verifast는 중간 카테고리의 고급 전류 도구입니다.객체 지향 패턴부터 고도로 동시적인 알고리즘 및 시스템 프로그램에 이르기까지 다양한 증거를 입증했습니다.
- 메조 프로그래밍 언어와 비동기 액체 분리 유형은 프로그래밍 언어의 유형 시스템에 CSL과 관련된 아이디어를 포함합니다.유형 시스템에 분리를 포함시키는 아이디어는 Alias Types 및 Syntaxic Control of Interference의 이전 예를 가지고 있습니다.

대화형 검증자와 중간 검증자의 차이는 명확하지 않습니다.예를 들어 Bedrock은 고도의 자동화를 위해 노력하고 있으며, Verifast에서는 인터랙티브 검증에 사용되는 전술(작은 프로그램)과 유사한 주석을 필요로 하는 경우가 있습니다.

레퍼런스

^ ^a ^b Reynolds, John C. (2002). "Separation Logic: A Logic for Shared Mutable Data Structures" (PDF). LICS.
^ Reynolds, John C. (1999). "Intuitionistic Reasoning about Shared Mutable Data Structure". In Davies, Jim; Roscoe, Bill; Woodcock, Jim (eds.). Millennial Perspectives in Computer Science, Proceedings of the 1999 Oxford–Microsoft Symposium in Honour of Sir Tony Hoare. Palgrave.
^ ^a ^b Ishtiaq, Samin; O'Hearn, Peter (2001). "BI as an Assertion Language for Mutable Data Structures". POPL. ACM: 14–26. doi:10.1145/360204.375719. ISBN 1581133367. S2CID 2652274.
^ O'Hearn, Peter; Reynolds, John C.; Yang, Hongseok (2001). "Local Reasoning about Programs that Alter Data Structures". CSL. CiteSeerX 10.1.1.29.1331.
^ Burstall, R. M. (1972). "Some techniques for proving programs which alter data structures". Machine Intelligence. 7.
^ O'Hearn, P. W.; Pym, D. J. (June 1999). "The Logic of Bunched Implications". Bulletin of Symbolic Logic. 5 (2): 215–244. CiteSeerX 10.1.1.27.4742. doi:10.2307/421090. JSTOR 421090. S2CID 2948552.
^ O'Hearn, Peter (February 2019). "Separation Logic". Commun. ACM. 62 (2): 86–95. doi:10.1145/3211968. ISSN 0001-0782.
^ Yang, Hongseok (2001). "An Example of Local Reasoning in BI Pointer Logic: the Schorr−Waite Graph Marking Algorithm". Proceedings of the 1st Workshop on Semantics' Program Analysis' and Computing Environments for Memory Management.
^ Hobor, Aquinas; Villard, Jules (2013). "The ramifications of sharing in data structures" (PDF). ACM SIGPLAN Notices. 48: 523–536. doi:10.1145/2480359.2429131.
^ Gardner, Philippa; Maffeis, Sergio; Smith, Hareth (2012). "Towards a program logic for Java Script" (PDF). Proceedings of the 39th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '12. pp. 31–44. doi:10.1145/2103656.2103663. hdl:10044/1/33265. ISBN 9781450310833. S2CID 9571576.
^ O'Hearn, Peter (2007). "Resources, Concurrency and Local Reasoning" (PDF). Theoretical Computer Science. 375 (1–3): 271–307. doi:10.1016/j.tcs.2006.12.035.
^ Hoare, C.A.R. (1972). "Towards a theory of parallel programming". Operating System Techniques. Academic Press.
^ Brookes, Stephen (2007). "A Semantics for Concurrent Separation Logic" (PDF). Theoretical Computer Science. 375 (1–3): 227–270. doi:10.1016/j.tcs.2006.12.034.
^ Dijkstra, Edsger W. Cooperating sequential processes (EWD-123) (PDF). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (등기) (1965년 9월)
^ Calcagno, Cristiano; O'Hearn, Peter W.; Yang, Hongseok (2007). "Local Action and Abstract Separation Logic" (PDF). 22nd Annual IEEE Symposium on Logic in Computer Science (LICS 2007). pp. 366–378. CiteSeerX 10.1.1.66.6337. doi:10.1109/LICS.2007.30. ISBN 978-0-7695-2908-0. S2CID 1044254.
^ Dinsdale-Young, Thomas; Birkedal, Lars; Gardner, Philippa; Parkinson, Matthew; Yang, Hongseok (2013). "Views" (PDF). ACM SIGPLAN Notices. 48: 287–300. doi:10.1145/2480359.2429104.
^ Sergey, Ilya; Nanevski, Aleksandar; Banerjee, Anindya (2015). "Specifying and Verifying Concurrent Algorithms with Histories and Subjectivity" (PDF). 24th European Symposium on Programming. arXiv:1410.0306. Bibcode:2014arXiv1410.0306S.
^ Gotsman, Alexey; Berdine, Josh; Cook, Byron; Sagiv, Mooly (2007). Thread Modular Shape Analysis (PDF). PLDI. Lecture Notes in Computer Science. Vol. 5403. pp. 266–277. doi:10.1007/978-3-540-93900-9_3. ISBN 978-3-540-93899-6.
^ https://www.eatcs.org/index.php/component/content/article/1-news/2280-2016-godel-prize-
^ 분리논리와 이연산, 페이지, 프로젝트 현장 추론.
^ 오픈소싱 페이스북 추론: 발송 전에 버그를 식별하십시오.C Calcagno, D 디스테파노, P'Hearn. 2015년 6월 11일
^ FSCQ 파일시스템 인증에 Crash Hoare Logic 사용, H Chen et al, SOSP'
^ OpenSSL HMAC의 정확성과 보안을 확인.Lennart Beringer, Adam Petcher, Katherine Q.네, 앤드류 W. 아펠입니다2015년 8월 제24회 USENIX 안보 심포지엄 개최
^ 프리엠프티브 OS 커널을 위한 실용적인 검증 프레임워크.펑웨이 쉬, 밍푸, 신유펑, 샤오란 장, 후이 장, 자오후이 리:CAV 2016: 59-79
^ 미국 하버드 대학 Ynot 프로젝트 홈페이지

[lics02-1] Reynolds, John C. (2002). "Separation Logic: A Logic for Shared Mutable Data Structures" (PDF). LICS.

[sl1999-2] Reynolds, John C. (1999). "Intuitionistic Reasoning about Shared Mutable Data Structure". In Davies, Jim; Roscoe, Bill; Woodcock, Jim (eds.). Millennial Perspectives in Computer Science, Proceedings of the 1999 Oxford–Microsoft Symposium in Honour of Sir Tony Hoare. Palgrave.

[popl01-3] Ishtiaq, Samin; O'Hearn, Peter (2001). "BI as an Assertion Language for Mutable Data Structures". POPL. ACM: 14–26. doi:10.1145/360204.375719. ISBN 1581133367. S2CID 2652274.

[csl01-4] O'Hearn, Peter; Reynolds, John C.; Yang, Hongseok (2001). "Local Reasoning about Programs that Alter Data Structures". CSL. CiteSeerX 10.1.1.29.1331.

[burstall-5] Burstall, R. M. (1972). "Some techniques for proving programs which alter data structures". Machine Intelligence. 7.

[bi-6] O'Hearn, P. W.; Pym, D. J. (June 1999). "The Logic of Bunched Implications". Bulletin of Symbolic Logic. 5 (2): 215–244. CiteSeerX 10.1.1.27.4742. doi:10.2307/421090. JSTOR 421090. S2CID 2948552.

[7] O'Hearn, Peter (February 2019). "Separation Logic". Commun. ACM. 62 (2): 86–95. doi:10.1145/3211968. ISSN 0001-0782.

[YangSchorrWaite-8] Yang, Hongseok (2001). "An Example of Local Reasoning in BI Pointer Logic: the Schorr−Waite Graph Marking Algorithm". Proceedings of the 1st Workshop on Semantics' Program Analysis' and Computing Environments for Memory Management.

[Ramifications-9] Hobor, Aquinas; Villard, Jules (2013). "The ramifications of sharing in data structures" (PDF). ACM SIGPLAN Notices. 48: 523–536. doi:10.1145/2480359.2429131.

[JavascriptLogic-10] Gardner, Philippa; Maffeis, Sergio; Smith, Hareth (2012). "Towards a program logic for Java Script" (PDF). Proceedings of the 39th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '12. pp. 31–44. doi:10.1145/2103656.2103663. hdl:10044/1/33265. ISBN 9781450310833. S2CID 9571576.

[11] O'Hearn, Peter (2007). "Resources, Concurrency and Local Reasoning" (PDF). Theoretical Computer Science. 375 (1–3): 271–307. doi:10.1016/j.tcs.2006.12.035.

[Hoare72-12] Hoare, C.A.R. (1972). "Towards a theory of parallel programming". Operating System Techniques. Academic Press.

[13] Brookes, Stephen (2007). "A Semantics for Concurrent Separation Logic" (PDF). Theoretical Computer Science. 375 (1–3): 227–270. doi:10.1016/j.tcs.2006.12.034.

[14] Dijkstra, Edsger W. Cooperating sequential processes (EWD-123) (PDF). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (등기) (1965년 9월)

[15] Calcagno, Cristiano; O'Hearn, Peter W.; Yang, Hongseok (2007). "Local Action and Abstract Separation Logic" (PDF). 22nd Annual IEEE Symposium on Logic in Computer Science (LICS 2007). pp. 366–378. CiteSeerX 10.1.1.66.6337. doi:10.1109/LICS.2007.30. ISBN 978-0-7695-2908-0. S2CID 1044254.

[16] Dinsdale-Young, Thomas; Birkedal, Lars; Gardner, Philippa; Parkinson, Matthew; Yang, Hongseok (2013). "Views" (PDF). ACM SIGPLAN Notices. 48: 287–300. doi:10.1145/2480359.2429104.

[17] Sergey, Ilya; Nanevski, Aleksandar; Banerjee, Anindya (2015). "Specifying and Verifying Concurrent Algorithms with Histories and Subjectivity" (PDF). 24th European Symposium on Programming. arXiv:1410.0306. Bibcode:2014arXiv1410.0306S.

[18] Gotsman, Alexey; Berdine, Josh; Cook, Byron; Sagiv, Mooly (2007). Thread Modular Shape Analysis (PDF). PLDI. Lecture Notes in Computer Science. Vol. 5403. pp. 266–277. doi:10.1007/978-3-540-93900-9_3. ISBN 978-3-540-93899-6.

[19] ttps://www.eatcs.org/index.php/component/content/article/1-news/2280-2016-godel-prize-

[20] 분리논리와 이연산, 페이지, 프로젝트 현장 추론.

[21] 오픈소싱 페이스북 추론: 발송 전에 버그를 식별하십시오.C Calcagno, D 디스테파노, P'Hearn. 2015년 6월 11일

[22] FSCQ 파일시스템 인증에 Crash Hoare Logic 사용, H Chen et al, SOSP'

[23] OpenSSL HMAC의 정확성과 보안을 확인.Lennart Beringer, Adam Petcher, Katherine Q.네, 앤드류 W. 아펠입니다2015년 8월 제24회 USENIX 안보 심포지엄 개최

[24] 프리엠프티브 OS 커널을 위한 실용적인 검증 프레임워크.펑웨이 쉬, 밍푸, 신유펑, 샤오란 장, 후이 장, 자오후이 리:CAV 2016: 59-79

[25] 미국 하버드 대학 Ynot 프로젝트 홈페이지

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[12]

[13]

[14]

[15]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

Search