Product Design, Manufacturing & Innovation Resources
» 형식적 검증

형식적 검증

1980
  • Edmund M. Clarke
  • E. Allen Emerson
  • Joseph Sifakis
Computer science engineer reviewing formal verification model in office.

(설명을 위한 생성된 이미지입니다)

공식적인 확인 형식 검증은 수학적 방법을 사용하여 시스템 설계가 형식 명세에 부합하는지 여부를 증명하거나 반증하는 것입니다. 특정 입력에 대해서만 버그의 존재를 보여줄 수 있는 테스트와 달리, 형식 검증은 모든 가능한 입력에 대해 버그가 없음을 증명할 수 있습니다. 형식 검증은 시스템의 형식 모델을 생성하고 모델 검증이나 정리 증명과 같은 기법을 사용하는 것을 포함합니다.

형식 검증은 시스템 정확성에 대한 최고 수준의 보증을 제공합니다. 이 과정은 시간 논리나 프로세스 대수와 같은 수학적 언어를 사용하여 시스템의 형식 모델을 생성하는 것으로 시작됩니다. 시스템 요구사항에서 도출된 속성 집합 또한 형식 언어로 표현됩니다. 그런 다음 검증 과정에서는 자동화된 도구를 사용하여 모델의 모든 가능한 상태를 체계적으로 탐색하고 지정된 속성이 참인지 여부를 판단합니다.

주로 사용되는 두 가지 기법은 모델 검증과 정리 증명입니다. 모델 검증은 유한 상태 모델의 전체 상태 공간을 탐색하는 자동화된 기법입니다. 특정 속성이 위반될 경우, 모델 검증기는 위반을 보여주는 구체적인 실행 추적인 반례를 생성합니다. 이 방법은 매우 효과적이지만, 매우 복잡한 시스템의 경우 '상태 공간 폭발' 문제에 직면할 수 있습니다. 정리 증명은 시스템과 그 속성을 논리 공식(정리)으로 표현하고 자동화된 또는 대화형 증명기를 사용하여 정확성에 대한 형식적인 증명을 구성하는 방식입니다. 이 접근 방식은 무한 상태 시스템을 처리할 수 있지만, 전문가의 상당한 수동 작업이 필요한 경우가 많습니다.

형식 검증은 계산 비용이 많이 들고 전문적인 지식을 요구하지만, 실패 시 비용이 매우 높은 안전 또는 보안 중요 시스템에는 필수적입니다. 철저한 테스트가 불가능한 CPU 부동 소수점 장치, 통신 프로토콜 및 제어 시스템의 정확성 검증에 성공적으로 적용되어 왔습니다.

UNESCO Nomenclature: 1203
컴퓨터 과학

유형

소프트웨어/알고리즘

분열

기초적인

용법

틈새/전문 분야

전구체

  • 명제 논리와 술어 논리
  • automata theory
  • 람다 미적분
  • 프로그램 의미론 (예: 호어 논리)
  • 계산 복잡도 이론

응용 프로그램

  • 마이크로프로세서 설계 (예: 인텔 펜티엄 F-Div 버그 수정)
  • 항공전자 소프트웨어(예: 플라이바이와이어 시스템)
  • 암호화 프로토콜 분석
  • 철도 신호 시스템
  • 중요 운영 체제용 소프트웨어 드라이버

특허:

NA

잠재적 혁신 아이디어

현재 하루 4만 건이 넘는 봇 트래픽을 차단하기 위해 이 콘텐츠는 커뮤니티 회원만 이용할 수 있습니다.
> 로그인 < 또는 >등록 < 이 콘텐츠를 비롯한 모든 제한된 콘텐츠와 도구는 (100% 무료로) 이용할 수 있습니다.

관련 분야: 형식 검증, 모델 검증, 정리 증명, 형식 방법론, 정확성, 소프트웨어 검증, 하드웨어 검증, 시간 논리.

역사적 맥락

형식적 검증

1970
1973
1980
1980
1980
1982-07-01
1988-06-01
1970
1970-01-01
1975-06-01
1980
1980
1980
1986-01-01
1990

(날짜를 알 수 없거나 관련이 없는 경우, 예를 들어 "유체역학"의 경우, 주목할 만한 등장 시기를 대략적으로 추정하여 제공합니다.)

관련 발명, 혁신 및 기술 원칙

고화질 이미지 및 다운로드는 등록된 회원에게만 100% 무료로 제공됩니다.

> 로그인 <