Codegate2020 Preliminary: Verifier

verifier.zip

0.00MB

정해진 문법에 맞추어 코드를 입력하면 실행해주는 프로그램이다.

 

입력한 코드를 a_interp를 통해 시뮬레이션을 돌려보고 에러가 없으면, interp를 통해 실제 구동을 한다.

 

플래그는 위와 같이 Print 구문을 통해 얻을 수 있다. 실제 구동에서 출력할 변수 값이 음수이면 플래그를 출력하는데, 시뮬레이션 도중 출력할 변수 값이 음수이면 print domain error을 발생시킨다.

 

IfElse, While, Cond, Num, Random 구문이 위 Print 구문처럼 시뮬레이션 코드와 실제 구동 코드가 다르다. 예시로 IfElse 구문을 살펴보자.

 

실제 구동 코드에서는 조건 값에 따라 실행하는 코드가 달라지고 그에 따라 변수의 값이 변하는데, 시뮬레이션의 경우 조건문에 사용되는 변수를 참이 되는 범위와 거짓이 되는 범위로 나누고 변수가 변할 수 있는 값의 범위를 확인한다. 간단히 하면, 시뮬레이션의 경우 변수가 변할 수 있는 모든 범위를 확인한다고 할 수 있다.

 

가능한 모든 범위를 확인하는 IfElse와 달리, While 구문의 경우 반복문을 5번만 실행해본다. 여기서 env_join은 코드를 실행한 후 변수의 값을 갱신하는 것이고, env_widen은 코드를 실행한 후 변수의 변경 추이에 따라 값이 증가하면 inf로, 값이 감소하면 -inf로 설정하는 것이다.

132줄을 통해 -inf, inf로 변한 값들 중 조건문에서 사용되는 변수의 경우 134줄의 cond.a_interp를 거치면서 -inf, inf값이 조건문의 범위에 맞게 변하지만, 그 이외의 변수들은 계속 -inf 혹은 inf값을 갖고 있는다.

 

그래서 위와 같은 코드에서 a가 음수가 될 수 없음에도 시뮬레이션 코드에서는 -inf가 되기 때문에 domain error가 발생한다.

우회 방법은 env_widen을 할 때 출력할 변수의 값을 감소시키지 않는 것이다.

따라서, 반복이 4번을 넘을 때부터 감소를 하면 되는데, 아래와 같이 안되는 방법도 있으니 주의해야 한다.

 

 위와 같은 방법은 136번줄에서 a의 범위가 -1~0이 되기 때문에 안된다.

 

위 코드의 경우 136번줄에서 a의 범위가 0~1이 되기 때문에 우회가 가능하다.

Flag: CODEGATE2020{4bstr4ct_1nt3rpr3tat10n_f0r_54f3_3v41uat10n}