두 개의 복잡한 프로그램이 동일하다는 것을 증명하려면 어떻게 해야 합니까?

Question

두 프로그램이 동등하다는 것을 증명하고 싶다고 가정해 보겠습니다. 엄격하게 가능하다면 또는 비공식적으로 그렇지 않은 경우).좀 더 구체적으로 말하자면, C로 구현된 HTTP 서버와 Node.js/JavaScript로 구현된 HTTP 서버와 같이 상대적으로 복잡한 것이 있다고 가정해 보겠습니다."이 둘은 사실상 동일하다"라고 말하면 어떻게 해야 합니까?내 옵션은 무엇입니까?무엇이 가능합니까?무엇이 불가능합니까?

프로그램 동등성 증명을 검토한 지 꽤 시간이 흘렀습니다(현재 다음 링크에 연결되어 있습니다). 이것, 하지만 아직 읽을 수는 없습니다. 하하, 평등 검사나 기본 루프와 같은 매우 간단한 프로그램에 초점을 맞추고 있는 것 같지만 강력한 HTTP 서버에 대해 묻고 있습니다.

본질적으로 (내 생각으로는) "JS와 C의 두 프로그램은 같은 일을 한다"고 말하고 싶습니다.저것 "같은 일을"라는 말은 분명 모호하지만 동시에 구체적인 의미를 담고 있습니다.두 시스템 모두에서 관찰 가능한 결과는 일반적으로 동일합니다. 주거나 받거나.그래서 그것은 증거와 같지만, 증거가 되지는 않습니다. 완벽한 증거.부분적인 증거인 것 같습니다.

나는 내 프로그램에 대해 "이 두 구현은 모든 의도와 목적에 대해 동일하다"고 말하고 싶습니다.아마도 성능 및 입력/출력 동작에 대한 측정 가능한 보증이나 관찰을 제공하는 것부터 시작한 다음 몇 가지 테스트를 작성하고 ...기억이 잘 나지 않습니다. 어떻게 든 시스템에 대해 설명합니다.아니면 그냥 "두 언어 모두에서 작동하는 HTTP 서버는 공리".그러면 단순화될 것입니다 :) 서로 동일한 작업을 수행한다고 가정하십시오.그러나 그것은 회피하는 것처럼 느껴집니다.

여기서 내 옵션이 무엇인지 궁금하십니까?이론적으로 이것을 어디까지 받아들일 수 있나요?구현하거나 정의하는 데 시간이 얼마나 걸릴지는 걱정하지 않습니다. 몇 년이 걸리더라도 괜찮습니다.나는 "C와 JS의 이 두 프로그램은 동등하다"는 진술을 보다 엄격하고 명확하게 만드는 측면에서 무엇이 가능한지 알고 싶습니다.이를 가능하게 하기 위해 어떤 기술/이론/연구 방향을 조사할 수 있습니까?

지금 나는 단지 가정 그것들은 암묵적으로 동일하므로 내 코드에서 ~전체 효과~가 동일하다는 것을 알고 C 함수나 JS 함수를 호출할 수 있습니다(모호합니다. 어떻게 고정해야 할지 모르겠습니다).가능하다면 좀 더 견고하게 만들 수 있도록 수학이나 모델 검사, 프로그램 시뮬레이션 등을 적용하고 싶습니다. :)

스펙트럼의 다른 쪽 끝에서는 다음을 증명하고 있습니다. 3 > 2 C와 JS 모두에서 동일합니다.이 간단한 경우에 내가 무엇을 해야 합니까?전체 HTTP 서버로 가는 길에 조금 더 복잡해지면 C에서 문자열을 복사하는 것은 JavaScript에서와 매우 다르지만 상대적으로 간단한 것입니다.두 언어 간의 "작업"이 동일하다는 것을 어디에서 증명하기 시작합니까?아니면 "증명"하지 않는다면 백업 증거 같은 것을 사용하여 동등하다고 "진술"하면 됩니다.

여기 많지는 않지만 이 다이어그램은 제가 기본적으로 하려는 작업입니다.

더 넓은 수준에서 문제는 다음과 유사한 것 같습니다....메달을 받고 싶다고 해보자.가게에 가서 하나 사거나 3D 프린팅할 수도 있어요.두 가지 "알고리즘"(상점 방문 또는 3D 프린팅)은 서로 많이 다르지만 사실상 동일합니다.이것이 동일하다는 것을 단계적으로 증명할 수 있는 간단한 방법은 없습니다. 운영상 (내 상상이 제공하는 것에서) 그러나 눈에 띄게 최종 결과는 동일합니다.(여기에서도) 이것을 엄격하게 어떻게 설명하시겠습니까?

Answer 1

오늘날 공식적인 분석은 일반적으로 모듈이나 단위 수준에서 수행됩니다.불행하게도 저는 공식적인 분석이 가능한지 예측할 수 있는 공통 측정 기준을 알지 못합니다.LOC 또는 최대 백만 개의 순환적 복잡성이 있어도 구조적으로 매우 간단한 코드만 형식적으로 분석할 수 있습니다.

귀하의 경우 두 프로그램 중 하나의 코드는 완전한 형식 분석을 하기에는 너무 복잡합니다.

• 모델 검사가 작동하지 않습니다.
• 완전한 (양방향) 시뮬레이션도 작동하지 않습니다.

그래서 제가 아는 가장 실용적인 해결책은 모델 기반 테스트.증거는 아니지만 공식적인 방법을 사용할 수 있습니다.궁극적으로 수동으로 작성된 테스트 사례를 작성하고 유지 관리하는 재난을 제거합니다.

추신.:

이 경우 수행할 수 있는 간단한 단계 목록은 다음과 같습니다.

• 두 프로그램의 추상 모델이 생성됩니다.이는 중요하지 않은 모든 세부 사항을 생략하는 세 번째 구현입니다.추상화는 이 모델이 공식적으로 분석될 만큼 충분히 단순하다는 장점이 있습니다.모델 분석기가 바이트 코드를 분석하는 경우 원하는 언어로 모델을 구현할 수 있습니다.
• 추상 모델은 순회될 수 있습니다.테스트 스위트에서 조건 적용 범위에 도달했습니다.이 단계는 모델 기반 테스트 도구를 사용하여 수행됩니다.
• 마지막으로 이러한 테스트 사례는 두 프로그램에서 테스트되고 추상 모델이 두 프로그램 구현을 시뮬레이션할 수 있는지 확인됩니다.
• 물론 이 시뮬레이션 관계는 동등성을 증명하는 것은 아닙니다.
• 추상화는 테스트에서 고려된 것과 생략된 것이 매우 깔끔한 사양입니다.
• 권장될 수 있는 두 가지 모델 기반 테스트 도구:Microsoft 사양 탐색기, Conformiq 디자이너

Answer 2

프로그램 동등성을 나타내는 전체 책 측량 기술을 작성할 수 있습니다. 이 답변은 매우 짧은 출발점입니다.

이론적으로, 당신이 튜링 기계로서 당신의 프로그램에 대해 생각한다면, 모든 희망은 손실된다. , 다시 $ \ 컵 $ 코어에 없습니다.

여전히 이론적으로, 기억의 일부로 메모리의 상태를 포함시킴으로써 유한 상태 시스템으로 프로그램에 대해 생각한다면 DFAS의 프로그램 동등성이 매우 간단합니다 (NL에서 solvable)이며, NFAS 완료 ...에 이 접근 방식의 문제는 상태 공간이 거대 할 것이라는 것입니다 (예 : 100 비트의 메모리 만 있으면, 주 공간이 $ 2 ^ {100} $ 주), 그래서 이것은 불합리합니다.

이제 이론적 인 경계를 해결 했으므로 운영시기를 정의하는 방법을 포함하여 이러한 주제를 해결하는 엄청난 작업을 해결합니다.

기본적으로 이것은 정식 검증 및 일부 키워드를 얻을 수있는 필드입니다. 당신은 시작했습니다 :

• 모델 검사
• bisimulation
• 추상화 - 정제
• 이론 프리버 (예 : Coq)

실제로 많은 회사가 공식적으로 코드를 확인합니다. 하드웨어의 경우 일반적인 관행이며 개발 중에 중요한 단계입니다. 소프트웨어의 경우, 엄청난 복잡성은 작은 비트 비트가 공식적으로 형식으로 입증되지만 전체 프로그램 (아직 적어도 적어도 아닙니다).