타입화된 확장 결정 다이어그램(TEDDs)을 통한 확장 가능한 확률적 프로그램 검증

최약 전제 기대치(Weakest pre-expectations)는 고전적 프로그램에서의 최약 전제 조건(weakest preconditions)에 대응하는 확률적 프로그램의 개념입니다. 연역적 검증(Deductive verification) 접근 방식은 이러한 정량적 기대치에 대한 경계(bounds)를 설정하는 것을 목표로 합니다. 이러한 자동화는 다양한 이산 확률적 프로그램(discrete probabilistic programs)을 분석하는 데 성공해 왔습니다. 그러나 해당 자동화의 핵심 루틴은 (부분적으로 언롤링된(unrolled)) 루프에 대한 추론을 필요로 하며, 이러한 언롤링에 대한 최약 전제 기대치의 논리적 표현은 종종 폭발적으로 증가합니다. 본 논문에서는 이진 결정 다이어그램(binary decision diagrams)의 다양한 확장 방식에서 영감을 얻은 타입화된 확장 결정 다이어그램(typed extended decision diagrams, TEDDs)을 개발합니다. 우리는 TEDDs로 표현된 WP(Weakest Preconditions)를 계산하는 방법, 표현을 더욱 축소하기 위한 SMT 기반 가지치기(pruning), 그리고 TEDDs에서 작동하도록 일부 증명 규칙(proof rules)을 격상(lift)시키는 방법을 보여줍니다. 마지막으로, TEDDs가 최첨단 기술(state of the art) 대비 연역적 확률적 프로그램 검증의 확장성(scalability)을 수 자릿수(orders of magnitudes)만큼 향상시킨다는 것을 입증합니다.