**형식 검증(Formal Verification)**은 “테스트로는 버그가 없음을 보장할 수 없다”는 말이 무슨 뜻인지, 그리고 수학적 증명이 소프트웨어에서 무엇을 보장하고 무엇은 보장하지 못하는지 이해할 때 핵심이 되는 개념입니다. 테스트·퍼징과의 차이부터 LLM이 증명을 작성할 때 달라지는 점까지 차례대로 살펴보겠습니다.

핵심 요약

형식 검증은 코드가 지켜야 할 규칙(명세)을 수학적으로 적고, 가능한 모든 입력에서 그 규칙을 지킨다는 것을 증명하는 방법입니다. 테스트와 퍼징은 고른 입력이나 무작위 입력만 확인하지만, 증명은 증명 검사기가 기계적으로 확인합니다. 다만 명세나 기계 모델이 현실과 다르면 “검증됨”이 “버그 없음”을 뜻하지는 않습니다.

형식 검증이란 무엇입니까?

한 줄 답: 코드를 수학적 모델로 옮긴 뒤, 정해진 규칙(명세)을 항상 지킨다는 증명을 작성해 증명 검사기로 기계적으로 확인하는 방법입니다.

형식 검증(formal verification)은 프로그램을 수학적 모델로 변환한 다음, 그 모델이 정의된 규칙 집합을 항상 따른다는 것을 수학적으로 증명하려는 접근입니다. 전체 흐름은 크게 세 단계로 나뉩니다.

  • 명세(specification, spec): 코드가 무엇을 해야 하고 무엇을 하지 말아야 하는지 정의한 규칙입니다. 프로그램의 올바름(correctness)은 전적으로 이 명세에 의해 정의됩니다.
  • 증명(proof): 코드의 수학적 모델이 명세를 만족한다는 논리적 유도 과정입니다. 증명 시도가 실패하면 코드에 버그가 있을 가능성이 있으며, 실패한 지점이 원인을 찾는 힌트가 됩니다. 개발자는 이를 수정하고 다시 증명을 시도합니다.
  • 증명 검사기(proof checker): 작성된 증명이 명세에 비추어 논리적으로 빈틈이 없는지 기계적으로 검사하는 도구(예: Rocq)입니다.

실제 프로그램에서 가장 큰 장벽 중 하나는 완전하고 모호하지 않은 명세(spec)를 얻기 어렵다는 점입니다. 명세가 빠뜨린 조건은 증명 대상에서도 빠지게 됩니다.

테스트·퍼징과는 무엇이 다릅니까?

한 줄 답: 테스트는 사람이 고른 입력만, 퍼징은 많은 무작위 변형 입력만 실행해 보지만, 형식 검증은 명세가 정한 범위의 모든 입력에 대해 성질을 증명합니다.

단위 테스트나 통합 테스트는 개발자가 직접 선택한 입력값에 대해서만 프로그램이 기대대로 동작하는지 확인합니다. 선택하지 않은 입력 경로에서 발생하는 오류는 찾지 못합니다.

퍼징(fuzzing)은 퍼저(fuzzer)가 진입점(entry point)에 반무작위로 변형한(semi-random, mutated) 대량의 입력을 계속 주입해 비정상 종료(crash)를 찾는 방식입니다. 오래 실행할수록 더 많은 문제를 찾을 수 있지만, 본질적으로 무차별 대입(brute force)이므로 모든 실행 경로를 거친다는 보장이 없습니다. 가능한 입력은 무한하므로 탐색이 완전히 끝날 수 없습니다.

반면 형식 검증은 명세가 정한 범위 안의 모든 입력에 대해 성질이 성립한다는 보편적 주장을 증명합니다. 예를 들어 기존 퍼즈 테스트를 “명시된 범위의 어떤 입력이 들어와도 이 테스트는 비정상 종료하지 않는다”라는 명세로 바꾼 뒤, 이를 해당 범위의 모든 입력에 대해 수학적으로 증명하는 식입니다.

input-space-ko

실행 중에 메모리 오류를 잡아내는 AddressSanitizer(ASan) 같은 런타임 검사 도구도 실제로 실행된 경로에서만 오류를 탐지할 수 있으며, 실행 시점 검사의 동작 방식은 「AddressSanitizer, 메모리 오류를 실행 중에 찾는 법」에서 확인할 수 있습니다.

“검증됨”은 무엇을 보장하고 무엇을 보장하지 못합니까?

한 줄 답: 명세와 기계 모델이 맞다는 가정 아래 증명된 정리만 보장하며, 명세 자체의 누락이나 실제 실행 환경과의 차이까지 막아 주지는 못합니다.

증명 검사기가 증명을 통과시켰더라도 여전히 사람이 신뢰해야 하는 기반이 있습니다.

  • 기계 및 OS 동작의 형식 모델: CPU 명령어 집합(instruction set)과 운영체제 프로세스 동작을 표현한 수학적 모델입니다.
  • 정확한 정리 문장(theorem statements): 무엇을 증명했는지 적힌 명세 그 자체입니다.
  • 증명 검사기 자체: 증명을 기계적으로 검증하는 도구(proof checker)입니다.

따라서 “형식적으로 검증됨(formally verified)“이 곧 “버그 없음(bug-free)“을 뜻하지는 않습니다. 증명 검사기는 명세가 현실과 일치하는지 판단할 수 없으며, 검증된 코드에서도 명세나 가정한 기계 의미론(semantics)이 현실과 다를 때 버그가 나타납니다. 예를 들어 증명이 대상으로 삼은 CPU나 링킹(linking) 환경이 실제 배포 환경과 다르면 모델이 설명하지 않은 동작이 일어날 수 있습니다. 또한 “비정상 종료”를 정의할 때 사용한 새니타이저(sanitizer)가 모든 메모리 안전성 버그를 잡지 못하거나, 모든 진입점을 다루지 않았거나, 호출자가 라이브러리를 잘못 사용하는 경우처럼 증명된 주장이 관심 있는 모든 문제를 포괄하지 못할 수도 있습니다.

trusted-base-ko

이와 관련해 Hacker News 토론에서도 명세 자체가 올바른지 어떻게 알 수 있는지—즉 제품을 올바르게 만들고 있는가(verification)와 올바른 제품을 만들고 있는가(validation)의 차이—그리고 증명이 동시성(concurrency) 문제까지 다루는지 등을 두고 논의가 이어졌습니다.

LLM이 증명을 쓰면 무엇이 달라집니까?

한 줄 답: 사람이 직접 쓰기에는 너무 크고 어려웠던 증명 작성 작업을 자동화하되, 결과의 참·거짓은 여전히 증명 검사기가 기계적으로 판정합니다.

역사적으로 형식 검증은 비용이 매우 높았습니다. 증명 코드가 원본 프로그램 코드보다 훨씬 커질 수 있고 전문적인 기술이 필요했기 때문에 주로 고신뢰·미션 크리티컬 분야에서만 제한적으로 쓰였습니다.

한 AI 연구 조직이 공개한 글(LLMs are making formal software verification feasible at a much larger scale)은 기존 퍼즈 테스트를 명세로 삼고 LLM이 증명을 작성하게 함으로써 이 증명 작성 작업을 대행할 수 있다고 주장합니다. 증명을 시도하는 과정에서 실제 코드의 버그가 발견되기도 했습니다.

여기서 핵심은 생성된 증명이 아무리 길고 복잡하더라도 사람이 세세하게 읽으며 검토할 필요가 없다는 점입니다. 증명 검사기(Rocq)가 명세에 맞는지 기계적으로 확인하기 때문입니다. 다만 LLM이 코드 패치까지 함께 수행할 때는 프로그램을 아예 비정상 종료하지 않는 자명한 코드로 다시 써서 정리를 쉽게 증명해 버리는 보상 해킹(reward hacking) 위험이 있으므로, 저자들은 이를 억제하고 패치를 직접 감사(audit)했다고 밝혔습니다.

자주 묻는 질문은 무엇입니까?

한 줄 답: C++26 계약(Contracts), ASan·Valgrind 같은 런타임 도구와의 관계, 그리고 현업에서 쓰이는 주요 증명 도구 이름을 정리했습니다.

C++ Contracts와는 어떤 관계입니까?

C++26 Contracts는 함수가 기대하는 조건을 코드에 명시해 설계에 따라 실행 중에 검사하는 기능인 반면, 형식 검증은 코드를 실행하지 않고 모든 입력에 대해 조건이 성립함을 증명한다는 점이 다릅니다. 계약 기능의 개념은 「C++26 Contracts란? pre·post·contract_assert로 함수 조건을 검사할 때」에서 다루고 있습니다.

형식 검증이 ASan을 대체합니까?

대체하지 않습니다. 런타임 도구는 실제 실행된 경로에서 오류를 찾고 증명은 명세와 형식 모델에 의존하므로 역할이 다르며, 앞서 소개한 연구에서도 “비정상 종료”를 정의할 때 모든 메모리 버그를 다 잡지는 못하는 ASan을 함께 사용했습니다. 런타임 메모리 검사 도구 간 차이는 「valgrind란? C/C++ 메모리 누수를 찾을 때 ASan과 차이」를 참고하시기 바랍니다.

일반 개발자도 쓸 수 있습니까?

목적과 언어에 따라 공개된 형식 검증 및 모델링 도구를 사용할 수 있으며, 대표적인 도구 이름으로는 증명 보조기인 Rocq와 Lean, Rust 코드 검증 도구인 Verus, 시스템 모델링 도구인 Alloy 등이 있습니다.

함께 보면 좋은 글은 무엇입니까?

한 줄 답: 런타임 메모리 오류 검사 도구, 자원 자동 해제 패턴, C++26 계약 기능을 다룬 글을 함께 참고하실 수 있습니다.

출처는 어디입니까?

한 줄 답: 본문 작성에 참고한 원문 연구 글과 커뮤니티 토론 출처입니다.