모델 체크

이 글은 검증을 위해 추가 인용문이 필요합니다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선하는 데 도움을 주십시오. 조달되지 않은 자재는 제거될 수 있습니다.출처 : '모델 체크'– 뉴스 · 신문 · 서적 · 학자 · JSTOR (2008년 11월) (이 템플릿 메시지 삭제 방법 및 삭제 시기 확인)

컴퓨터 과학에서 모델 검사 또는 속성 검사는 시스템의 유한 상태 모델이 주어진 규격(정확성이라고도 함)을 충족하는지 확인하는 방법입니다.이는 일반적으로 하드웨어 또는 소프트웨어 시스템과 관련되어 있으며, 사양에는 안전 요건(시스템 충돌을 나타내는 상태의 회피 등)뿐만 아니라 활성 요건(라이브록 방지 등)이 포함되어 있습니다.

이러한 문제를 알고리즘적으로 해결하기 위해 시스템의 모델 및 사양은 모두 어떤 정밀한 수학 언어로 공식화된다.이를 위해 이 문제는 논리에서의 태스크, 즉 구조가 주어진 논리식을 만족하는지 여부를 확인하는 것으로 공식화된다.이 일반적인 개념은 많은 종류의 논리와 많은 종류의 구조에 적용된다.단순한 모델 체크 문제는 명제 논리의 공식이 주어진 구조에 의해 충족되는지 확인하는 것으로 구성됩니다.

개요

속성 확인은 두 설명이 동일하지 않을 때 검증에 사용됩니다.세분화 중에 사양은 상위 사양에서 불필요한 세부 정보로 보완됩니다.이것은 불가능하기 때문에 새로 도입된 속성을 원래 사양과 비교하여 확인할 필요가 없습니다.따라서 엄격한 양방향 동등성 검사는 단방향 속성 검사로 완화됩니다.구현 또는 설계는 시스템의 모델로 간주되는 반면, 사양은 모델이 ^[2]충족해야 하는 속성입니다.

사양이 시간 논리식에 의해 주어지는 하드웨어 및 소프트웨어 설계의 모델을 확인하기 위해 모델 검사 방법의 중요한 클래스가 개발되었다.시간 논리 사양의 선구적인 작업은 Amir Pnueli에 의해 이루어졌으며, 그는 "시간 논리를 컴퓨팅 ^[3]과학에 도입하는 세미날 작업"으로 1996년 튜링 상을 받았습니다.모델 체크는 E. M. 클라크, E. A.^[4][5][6] 에머슨, J. P. 케일,^[7] J. 시파키스의 선구적인 작업으로 시작되었습니다.Clarke, Emerson 및 Sifakis는 모델 ^[8][9]체크 분야를 설립하고 발전시킨 중요한 업적으로 2007년 Turing Award를 공동 수상했습니다.

모델 체크는 하드웨어 설계에 가장 많이 적용됩니다.소프트웨어의 경우, 결정 불가능성(계산 가능성 이론 참조) 때문에 접근방식은 완전한 알고리즘이 될 수 없고, 모든 시스템에 적용되며, 항상 답을 줄 수 없다. 일반적인 경우, 주어진 속성을 증명하거나 반증하는 데 실패할 수 있다.임베디드 시스템 하드웨어에서는 UML 활동도^[10] 또는 제어 해석된 페트리망을 ^[11]통해 전달된 규격을 검증할 수 있습니다.

이 구조는 일반적으로 산업용 하드웨어 기술 언어 또는 특수 목적 언어로 소스 코드 기술로서 제공됩니다.이러한 프로그램은 유한 상태 기계(FSM), 즉 노드(또는 정점)와 가장자리로 구성된 유향 그래프에 대응합니다.원자 명제 세트는 각 노드에 관련지어지며, 일반적으로 어떤 메모리 요소가 하나인지를 나타냅니다.노드는 시스템 상태를 나타내고, 에지는 상태를 변경할 수 있는 가능한 전이를 나타내며, 원자 명제는 실행 시점에 유지되는 기본 속성을 나타냅니다.

문제는 다음과 같이 나타낼 수 있습니다.필요한 속성(시간 $p\displaystyle$ p$)$ 및 $초기{\displaystyle }$ $상태{\displaystyle }$s$\displaystyle$ s$\backslash$$displaystyle$M$\models$ p$\$$displaystyle$ M$\$displaystyle p\displaystyle m$\backslash$models로 표현)이 M$,$ ${\displaystyle s\backslash }$$displaystyle$ $M$이 $유한$한지 여부를 ${\displaystyle \mathrm{결정}}$합니다.제품, 모델 확인은 그래프 검색으로 감소합니다.

심볼 모델 확인

이 섹션은 확장해야 합니다.추가함으로써 도움이 될 수 있습니다. (2011년 1월)

도달 가능한 상태를 한 번에 하나씩 열거하는 것이 아니라 한 번에 다수의 상태를 고려함으로써 상태 공간을 보다 효율적으로 통과할 수 있습니다.이러한 상태-공간 통과가 논리식, 이진 결정 다이어그램(BDD) 또는 기타 관련 데이터 구조로서의 상태 집합 및 전이 관계의 표현에 기초하고 있는 경우, 모델 검사 방법은 상징적이다.

역사적으로 첫 번째 상징적 방법은 BDD를 사용했다. 1996년 인공 지능의 계획 문제를 해결하는 명제적 만족도(satplan 참조)가 성공한 후, 동일한 접근방식이 선형 시간 논리(LTL)에 대한 모델 확인에 일반화되었다. 즉, 계획 문제는 안전 특성에 대한 모델 확인에 해당한다.이 방법을 경계 모델 ^[12]검사라고 합니다.경계 모델 검사에서 부울 만족도 솔버의 성공은 기호 모델 ^[13]검사에서 만족도 솔버의 광범위한 사용으로 이어졌다.

예

이러한 시스템 요건의 한 예: 엘리베이터가 층에 호출된 후 해당 층에서 문을 연 후 엘리베이터는 최대 두 번 그 층에 도착할 수 있습니다."Finite-State Verification을 위한 Property Specifications in Finite-State Verification"의 저자는 이 요건을 다음과 같은 LTL ^[14]공식으로 변환합니다.

${\displaystyle{\begin{정렬}\Box((call\lor \Diamond 열려)\to&((\lnot atfloor\lor 개방 \lnot)~{{U\mathcal}}\\&,(open\lor((atfloor\land \lnot 열려)~{{U\mathcal}}\\&,(open\lor((\lnot atfloor\land 개방 \lnot)~{{U\mathcal}}\\&,(open\lor((atfloor\land \lnot 열려)~{{U\mathcal}}\\&,(open\lor(\lnot atfloor~{{U}\mathcal}~open))).))))))))\end{정렬}}}$

여기서 $◻(\$$displaystyle$$\Box)$는 "항상$display$(\displaystyle $\Diamond)$는 "결국",$$U$(\displaystyle$ {$U})$는 "until$$$$", 기타 기호는${\displaystyle }$"$또는$$$"displaystyle$\l"$이 아닌 표준 논리 기호입니다$.{\displaystyle \mathrm{}}$또는 "아니요"를 선택합니다.

기술

모델 체크 도구는 상태 폭발 문제로 알려진 상태 공간의 조합적 폭발에 직면하며, 이러한 문제는 대부분의 실제 문제를 해결하기 위해 해결해야 합니다.이 문제를 해결하기 위한 몇 가지 방법이 있습니다.

1. 기호 알고리즘은 FSM(Finite State Machine)에 대한 그래프를 명시적으로 구성하는 것을 피하며, 대신 정량화된 명제 로직의 공식을 사용하여 암시적으로 그래프를 나타냅니다.BDD(binary decision diagram)의 사용은 Ken McMillan의^[15] 연구와 CUDD^{[16] [17]}및 BuDDy와 같은 오픈 소스 BDD 조작 라이브러리의 개발에 의해 대중화되었습니다.
2. 한정 모델 체크 알고리즘은 고정된 스텝 $수{\displaystyle }$ k${displaystyle$ k$\}$에 대해 FSM을 전개하고 k${displaystyle$ k$}$ 이하의$$ $스텝$에서 속성 위반이 발생할 수 있는지 확인합니다.여기에는 일반적으로 제한된 모델을 SAT 인스턴스로 인코딩하는 작업이 포함됩니다.가능한 모든 위반이 배제될 때까지 k$(\displaystyle$ k$)$의 값을$$ 점점 더 크게 하여 프로세스를 반복할 수 있습니다(cf).심도 우선 검색을 반복한다).
3. 추상화는 먼저 단순화함으로써 시스템의 속성을 증명하려고 합니다.단순화된 시스템은 일반적으로 원래의 것과 정확히 동일한 특성을 만족시키지 못하기 때문에 개선 과정이 필요할 수 있습니다.일반적으로 추상화가 건전해야 한다(추상화에서 증명된 속성은 원래 시스템에 대한 진실이다). 그러나 때때로 추상화가 완전하지 않다(원래 시스템의 모든 진정한 속성이 추상화에 대한 진실인 것은 아니다).추상화의 한 예는 비부울 변수의 값을 무시하고 부울 변수와 프로그램의 제어 흐름만을 고려하는 것이다. 이러한 추상화는 거칠게 보일 수 있지만, 사실 상호 배제의 특성을 증명하기에 충분할 수 있다.
4. CEGAR(Countele-guided abstraction refinement)는 거친(즉, 부정확한) 추상화에서 확인을 시작하고 반복적으로 이를 수정한다.위반(예: 반례)이 발견되면 툴은 실현 가능성을 분석합니다(예: 위반이 진짜인지 불완전한 추상화의 결과인지).위반이 가능한 경우 사용자에게 보고됩니다.그렇지 않은 경우 실행 불가능한 증명은 추상화를 구체화하기 위해 사용되며 검사가 ^[18]다시 시작됩니다.

모델 검사 도구는 처음에는 이산 상태 시스템의 논리적 정확성을 추론하기 위해 개발되었지만, 이후 실시간 및 제한된 형태의 하이브리드 시스템을 다루도록 확장되었습니다.

1차 논리

모델 체크는 계산 복잡도 이론 분야에서도 연구된다.특히 1차 논리식은 자유 변수 없이 고정되며 다음과 같은 결정 문제가 고려됩니다.

예를 들어 관계형 데이터베이스로 기술된 유한한 해석이 주어진 경우 해당 해석이 공식의 모델인지 여부를 결정한다.

이 문제는 회선 클래스⁰ AC에 있습니다.입력 구조에 몇 가지 제한을 가할 때 다루기 쉽다. 예를 들어, 상수(일반적으로 모노딕 2차 로직에 대한 모델 확인의 트랙터빌리티를 의미함)에 의해 제한되는 트리 너비를 요구하는 것, 모든 도메인 요소의 정도, 그리고 유계 확장, 로컬 bou와 같은 보다 일반적인 조건을 제한한다.nded 확장과 어디에도 없는 구조입니다.^[19]이러한 결과는 자유 ^{[citation needed]}변수가 있는 1차 공식에 대한 모든 솔루션을 열거하는 작업으로 확장되었습니다.

도구들

다음은 중요한 모델 검사 도구 목록입니다.

• 합금(합금 분석기)
• BLAST(Berkeley Lazy Abstraction 소프트웨어 검증 도구)
• 통신 프로토콜 및 분산 시스템 설계를 위한 도구 상자인 CADP(분산 프로세스 구축 및 분석)
• CPAchecker: CPA 프레임워크에 기반한 C 프로그램용 오픈 소스 소프트웨어 모델 검사기
• ECLAIR: C 및 C++ 프로그램의 자동 분석, 검증, 테스트 및 변환을 위한 플랫폼
• FDR2: CSP 프로세스로 모델링 및 지정된 실시간 시스템을 검증하는 모델 체커
• MPI 프로그램의 ISP 코드레벨 검증자
• Java Pathfinder: Java 프로그램용 오픈 소스 모델 검사기
• Libdmc: 분산 모델 확인을 위한 프레임워크
• mCRL2 툴셋, 부스트 소프트웨어 라이선스, ACP 기반
• NuSMV: 새로운 심볼 모델 체커
• PAT: 동시 및 실시간 시스템을 위한 향상된 시뮬레이터, 모델 체커 및 정밀 검사기
• 프리즘: 확률론적 심볼 모델 체커
• Roméo: 파라미터, 시간 및 스톱워치 Petri 네트로 모델링된 실시간 시스템의 모델링, 시뮬레이션 및 검증을 위한 통합 도구 환경
• SPIN: 엄밀하고 대부분 자동화된 방법으로 분산 소프트웨어 모델의 정확성을 검증하는 일반적인 도구
• TAPAs: 프로세스 대수 분석을 위한 도구
• TAPAAL: Timed-Arc Petri Nets 모델링, 검증 및 검증을 위한 통합 도구 환경
• Leslie Lamport의 TLA+ 모델 체커
• UPPAAL: 실시간 시스템의 모델링, 검증 및 검증을 위한 통합 도구 환경
• Zing^[20] – 마이크로소프트의 실험 툴로 소프트웨어 상태 모델을 다양한 수준에서 검증합니다.개요 수준의 프로토콜 설명, 워크플로우 사양, 웹 서비스, 디바이스 드라이버 및 운영 체제의 핵심 프로토콜입니다.Zing은 현재 Windows용 드라이버 개발에 사용되고 있습니다.

「 」를 참조해 주세요.

레퍼런스

추가 정보

• 모델 체크, 도론 A Peled, Patrizio Pelliccione, Paola Spoletini, Wiley Encyclopedia of Computer Science and Engineering, 2009.
• 모델 체크, 에드먼드 M. 클라크, 오르나 그루버그 및 도론 A.Peled, MIT Press, 1999, ISBN 0-262-03270-8.
• 시스템 및 소프트웨어 검증: 모델 확인 기법 및 도구, B.Berard, M. Bidoit, A.핀켈, F. 라루시니, A.쁘띠, L. 페트루치, P. 슈노벨렌, ISBN 3-540-41523-8
• 컴퓨터 사이언스에서의 논리: 시스템에 관한 모델링과 추론, Michael Huth와 Mark Ryan, Cambridge University Press, 2004.
• 스핀 모델 검사기: 입문 및 참조 설명서, Gerard J. Holzmann, Addison-Wesley, ISBN 0-321-22862-6.
• Julian Bradfield와 Colin Stirling, Modal Logics and mu-beaki, Inf.ed.ac.uk
• 사양 패턴 KSU.edu
• RAFMC 속성 패턴 매핑(Inria.fr
• Radu Mateescu 및 Mihaela Shireanu Efficient On-the-fly 모델체크 - 정기적인 교대 없는 Mu-Calculus, 6페이지, 컴퓨터 프로그래밍 과학 46:255–281, 2003
• Muller-Olm, M., Schmidt, D.A. 및 Steffen, B.모델 체크: 튜토리얼 소개.제6회 정적 분석 심포지엄, G. 파일 및 A.Corteshi, ed., Springer LNCS 1694, 1999, 페이지 330-354.
• Baier, C., Katoen, J.: 모델 체크의 원칙.2008.
• E.M. Clarke: '모델 체크의 탄생' doi: 10.1007/978-3-540-69850-0_1
• E. 앨런 에머슨(2008년)."모델 체킹의 기원:개인 관점".Orna Grumberg;헬무트 Veith(eds.)이다. 모델 체킹— 역사의 25년 Achievements, 전망.LNCS.Vol5000.하이델베르크:스프링거.를 대신하여 서명함. 27–45. doi:10.1007/978-3-540-69850-0_2.아이 에스비엔 978-3-540-69849-4.(모델의 이것 또한 매우 좋은 소개와 개요를 확인하고).