경로구분 정적 문자열분석

Abstract

웹 애플리케이션이나 데이터베이스 애플리케이션 등의 프로그램은 실행 중 외부에서 들어온 문자열을 프로그램에서 기획한 대로 조합하여 다른 메시지나 SQL질의, 프로그램, HTML문서등을 생성하는데 사용한다. 이 문자열은 프로그램이 실행하는 과정에서 완성된다. 애플리케이션이 생성할 문자열을 실행 전에 미리 예측할 수 있다면, 문법 검사, 취약점 검사 등을 사전에 수 행할 수 있다. 프로그램의 문자열 계산식의 값을 정적으로 예측하는 것을 문자열분석이라 한다. 문자열분석을 수행하게 되면 그 결과는 문자열을 요약한 어떤 값으로 나타내야 한다. 일반적으로 정규표현식이나 문맥자유문법과 같은 형식문법을 사용하게 되는데, 문맥자유문법으로 요약할 경우 그에 대한 문법검사 등은 비결정적이기 때문에 사용에 제약이 많이 따른다. 또한, 정규표현식으로 요약할 경우 문법검사 등은 용이하지만 결과의 거짓양성이 많이 발생하여 정밀도가 떨어진다. 실행경로 요약에서 발생하는 거짓양성을 최소화하기 위해서 조건 분기문 등의 조건에 대한 참 또는 거짓을 만족하는 각각의 환경을 분리하는 경로민감 분석을 도입하게 된다. 일반적으로 경로민감 분석은 조건 분기문의 참 또는 거짓을 만족하는 각각의 환경을 제약식으로 만들고, 그것의 해를 구하는 것으로 각각의 실행경로에서의 보다 정확한 값을 구하게 된다. 경로민감 분석에서는 각 실행경로에 대한 제약식을 잘 풀기위한 방법들이 제시되어야 하는데, 제약식 풀이기를 사용하더라도 일반적으로 매우 비용이 많이 든다. 본 논문에서는, 문자열분석에 있어서 결과 거짓양성을 줄이면서도 그 비용이 많이 증가하지 않는 경로구분 문자열분석을 제안한다. 경로구분분석은 가벼운 방식의 경로민감 분석이다. 조건 분기문의 조건이 참 또는 거짓이 되는 조건은 무시하지만, 다른 실행경로에서 저장되거나 계산된 값들이 함께 계산되지 않도록 하기 위해 저장되거나 계산된 값에 대해 실행경로를 유지한다. 이는 문자열 값을 분석할 때, 조건을 만족하는 환경들과는 무관하게 각각 분리된 경로에서 만들어진 값이 함께 조합될 때 발생하는 거짓양성이 더 많기 때문에 유용하다. 먼저 경로요소가 없는 문자열분석을 요약해석 프레임워크에 기반을 두고 정의한다. 문자열 요약을 위해 정규문자열을 정의하고, 분석종료를 만족시키기 위해 넓히기 연산을 정의한다. 그 다음 이를 경로구분 문자열분석으로 확장한다. 요약경로를 정의하고, 요약경로를 계산하기 위한 경로계산법를 기술한다. 끝으로, 분석정의를 기반으로 한 경로구분 문자열분석기를 구현하고 실험하여 그 유용성과 실용성을 보인다.