하루 만에 4개 주요 데이터베이스에서 100개 이상의 취약점을 자동으로 발견한 저장대학교 연구는 SIGMOD 2023에서 최고의 논문을 수상했습니다.

2023 ACM SIGMOD/PODS 데이터 관리에 관한 국제 컨퍼런스(SIGMOD 2023)가 현지 시간으로 6월 18일부터 23일까지 미국 시애틀에서 개최됩니다. 최근 컨퍼런스에서는 Microsoft Research의 "Predicate Pushdown for Data Science Pipelines"와 Zhejiang University의 "Detecting Logic Bugs of Join Optimizations in DBMS"가 우승을 차지한 최고의 논문 목록을 발표했습니다. 1975년 학회 창립 이래 중국 본토 연구팀이 최우수 논문상을 수상한 것은 이번이 처음이다. 그 중 절강대학교 연구에서는 MySQL, MariaDB, TiDB, PolarDB 등 데이터베이스 관리 시스템의 논리적 취약점을 자동으로 발견할 수 있는 새로운 방법을 제안했습니다.

지난 수십 년 동안 최신 데이터베이스 관리 시스템(DBMS)은 쿼리 평가에 점점 더 복잡하고 정교한 최적화가 필요한 클라우드 플랫폼 및 HTAP와 같은 다양한 새로운 아키텍처를 지원하도록 계속해서 발전해 왔습니다. 쿼리 최적화 프로그램은 DBMS에서 가장 복잡하고 중요한 구성 요소 중 하나로 간주됩니다. 그 기능은 입력 SQL 쿼리를 구문 분석한 다음 내장된 비용 모델의 도움을 받아 효율적인 실행 계획을 생성하는 것입니다. 쿼리 최적화 프로그램 구현 오류로 인해 충돌 취약점 및 논리 허점을 비롯한 취약점(버그)이 발생할 수 있습니다. 충돌로 인해 시스템이 즉시 중지되므로 충돌 취약성을 쉽게 감지할 수 있습니다. 그러나 논리 취약점은 DBMS가 감지하기 어려운 잘못된 결과 집합을 반환하게 할 수 있기 때문에 쉽게 간과됩니다. 이 문서에서는 이러한 조용한 취약점을 탐지하는 데 중점을 둡니다.

DBMS의 논리적 취약점을 탐지하는 새로운 접근 방식, 즉 PQS(피벗 쿼리 합성)가 있습니다. 이 방법의 핵심 아이디어는 테이블에서 피벗 행(피벗 행)을 무작위로 선택한 다음 이 행을 결과로 사용하여 쿼리를 생성하는 것입니다. 합성된 쿼리가 해당 데이터 행을 반환할 수 없으면 논리 취약점이 감지된 것입니다. PQS는 주로 단일 테이블에서 옵션 쿼리를 지원하는 데 사용되며 보고된 취약점의 90%는 단일 테이블 쿼리에만 관련됩니다. 다양한 조인 알고리즘과 조인 구조(단일 테이블 쿼리보다 오류가 발생하기 쉬운)를 사용하는 다중 테이블 쿼리에 대해서는 여전히 연구 격차가 큽니다.

다음 그림은 MySQL에서 두 조인 쿼리의 논리적 취약성을 보여줍니다. 두 가지 취약점 모두 이 문서에서 제안된 새로운 도구를 사용하여 탐지할 수 있습니다.

그림 1: DBMS

그림 1(a)는 MySQL 8.0.18의 해시 조인의 논리적 취약점을 보여줍니다. 이 예에서 첫 번째 쿼리는 블록 중첩 루프 조인을 사용하여 실행되므로 올바른 결과 집합을 반환합니다. 그러나 내부 해시 조인을 사용한 두 번째 쿼리가 잘못되어 잘못 비어 있는 결과 집합이 반환되었습니다. 이는 기본 해시 조인 알고리즘이 0이 -0과 같지 않다고 잘못 가정하기 때문입니다.

그림 1(b)의 논리 취약점은 MySQL 8.0.28의 semi-join 처리에서 비롯됩니다. 첫 번째 쿼리에서 중첩 루프 내부 조인은 varchar 데이터 유형을 bigint로 변환하여 올바른 결과 집합을 생성합니다. 해시 세미 조인을 사용하여 두 번째 쿼리를 실행하면 varchar 데이터 유형이 double로 변환되어 동등한 비교에서 데이터 정확도가 떨어지고 오류가 발생합니다.

다중 테이블 조인 쿼리의 논리적 취약점 감지 문제에 쿼리 합성 방법을 사용하는 것은 단일 테이블 쿼리보다 훨씬 어렵습니다.

• 결과 검증: 이전 방법에서는 쿼리 결과의 정확성을 검증하기 위해 차등 테스트 전략을 사용했습니다. 아이디어는 쿼리를 처리하기 위해 다양한 물리적 실행 계획(데이터베이스 시스템이 실제로 쿼리 문을 실행하는 방식)을 사용하는 것입니다. 이러한 계획이 일관되지 않은 결과 세트를 반환하는 경우 논리 결함이 감지되었을 수 있습니다. 그러나 차등 테스트 방법에는 두 가지 단점이 있습니다. 첫째, 특정 논리적 취약점은 여러 물리적 실행 계획에 영향을 주어 모두 동일한 잘못된 결과를 생성할 수 있습니다. 둘째, 일관되지 않은 결과 집합이 관찰되면 어떤 실행 계획이 올바른 결과를 생성했는지 수동으로 확인하는 데 비용이 많이 듭니다. 이 문제에 대한 가능한 해결책은 임의 테스트 쿼리에 대한 실제 결과를 구성하는 것이지만 기존 도구는 이 작업을 지원하지 않습니다.
• 검색 공간: 특정 데이터베이스 스키마에 대해 생성할 수 있는 조인 쿼리 수는 다양합니다. 테이블과 열의 개수가 기하급수적으로 늘어납니다. 검증을 위해 가능한 모든 쿼리를 열거하는 것은 불가능하므로 논리적 취약점을 최대한 효율적으로 탐지할 수 있는 효과적인 쿼리 공간 탐색 메커니즘이 필요합니다.

위 문제에 대응하여 저장대학교 연구진은 TQS(Transformed Query Synesis)라는 방법을 제안했습니다. TQS는 DBMS의 조인 최적화에서 논리적 취약점을 탐지하는 작업을 위한 새롭고 보편적이며 비용 효과적인 도구입니다.

위의 첫 번째 과제에 대응하여 연구진이 제안한 솔루션은 DSG, 즉 Data-guided Schema and query Generation(Data-guided Schema and query Generation)입니다. 넓은 테이블로 표현된 데이터 세트가 주어지면 DSG는 감지된 패러다임을 기반으로 데이터 세트를 여러 테이블로 분할할 수 있습니다. 취약점 발견 속도를 높이기 위해 DSG는 생성된 데이터베이스에 일부 인공 노이즈 데이터도 삽입합니다. 먼저 데이터베이스 스키마를 그래프로 변환합니다. 여기서 노드는 테이블/열이고 가장자리는 노드 간의 관계입니다. DSG는 패턴 그래프에서 무작위 탐색을 사용하여 쿼리용 테이블을 선택한 다음 이 테이블을 사용하여 조인을 생성합니다. 여러 테이블이 포함된 특정 조인 쿼리의 경우 넓은 테이블에서 실제 결과를 쉽게 찾을 수 있습니다. 이러한 방식으로 DSG는 데이터베이스 유효성 검사를 위한 컬렉션(쿼리, 결과)을 효과적으로 생성할 수 있습니다.

위의 두 번째 과제를 해결하기 위해 연구원이 고안한 방법은 지식 기반 쿼리 공간 탐색 인 KQE입니다. 이 방법은 패턴 그래프를 전체 쿼리 생성 공간을 나타내는 계획-반복 그래프로 확장하는 것으로 시작됩니다. 그러면 각 조인 쿼리가 하위 그래프로 표시됩니다. 생성된 쿼리 그래프의 점수를 매기기 위해 KQE는 이미 탐색된 공간에서 구조적으로 유사한 쿼리 그래프를 검색하는 임베딩 기반 그래프 인덱스를 사용합니다. 랜덤 워크 쿼리 생성기는 커버리지 점수를 기반으로 안내되어 알려지지 않은 쿼리 공간을 최대한 많이 탐색합니다.

방법의 다양성과 효율성을 입증하기 위해 연구원들은 일반적으로 사용되는 4가지 DBMS인 MySQL, MariaDB, TiDB 및 PolarDB에서 TQS를 평가했습니다. TQS는 24시간 동안 실행한 후 MySQL에서 31개, MariaDB에서 30개, TiDB에서 31개, PolarDB에서 23개를 포함하여 115개의 취약점을 성공적으로 발견했습니다. 근본 원인을 분석하면 이러한 취약점의 유형을 요약할 수 있는데, 그 중 MySQL의 취약점은 7가지 유형, MariaDB의 경우 5가지 유형, TiDB의 경우 5가지 유형, PolarDB의 경우 3가지 유형이 있습니다. 연구진은 발견된 취약점을 해당 커뮤니티에 제출했으며 긍정적인 피드백을 받았습니다.

다음은 해결해야 할 문제와 절강대학교에서 제안한 솔루션을 수학적인 형태로 설명합니다.

문제 정의

데이터베이스 취약점에는 충돌과 논리적 취약점이라는 두 가지 유형이 있습니다. 크래시 취약점은 운영 체제 및 DBMS 실행으로 인해 발생합니다. 메모리 등 리소스 부족, 잘못된 메모리 주소 접근 등의 이유로 DBMS가 강제 종료될 수 있습니다. 따라서 충돌 취약점을 쉽게 발견할 수 있습니다. 데이터베이스는 여전히 정상적으로 실행되고 쿼리를 처리하며 겉으로는 올바른 결과를 반환하기 때문에 논리 취약점을 찾기가 훨씬 더 어렵습니다(대부분의 경우 그렇게 하지만 일부 경우에는 잘못된 결과 집합을 읽을 수도 있음). 이러한 소리 없는 취약점은 눈에 보이지 않는 폭탄과도 같으며 감지하기 어렵고 애플리케이션의 정확성에 영향을 미칠 수 있기 때문에 더욱 위험합니다.

이 문서에서는 다중 테이블 조인 쿼리 문제에 대한 논리적 취약점을 탐지하는 쿼리 최적화 프로그램을 소개합니다. 연구원들은 이러한 취약점을 최적화 버그에 합류한다고 부릅니다. 표 1에 제공된 표기법을 사용하여 조인 최적화 취약점 탐지 문제는 다음과 같이 공식적으로 정의될 수 있습니다.

정의: 쿼리 워크로드 Q의 각 쿼리 qi에 대해 쿼리 최적화 프로그램이 여러 실제 계획 연결을 통해 qi를 실행하고 검증하도록 합니다. Ground Truth 를 사용하여 결과 집합 . 인 경우 연결 최적화 취약점이 발견되었습니다.

표 1: 기호 설명 테이블

프로젝트 개요

그림 2는 TQS의 아키텍처 개요를 제공합니다. 기본 데이터 세트와 대상 DBMS가 주어지면 TQS는 데이터 세트를 기반으로 쿼리를 생성하여 DBMS에서 가능한 논리적 취약점을 검색합니다. TQS에는 데이터 기반 스키마 및 쿼리 생성(DSG)과 지식 기반 쿼리 공간 탐색(KQE)이라는 두 가지 주요 구성 요소가 있습니다. 입력 데이터 세트는 넓은 테이블로 처리되며 원래 튜플 외에도 DSG는 의도적으로 오류가 발생하기 쉬운 값(예: Null 값 또는 매우 긴 문자열)을 사용하여 일부 튜플을 합성합니다. 조인 쿼리의 경우 DSG는 와이드 테이블을 여러 테이블로 분할하여 테이블이 기능적 종속성 기반 패러다임을 준수하는지 확인함으로써 와이드 테이블에 대한 새 스키마를 생성합니다. DSG는 데이터베이스 스키마를 그래프로 모델링한 다음 스키마 그래프에서 무작위 탐색을 통해 논리적/개념적 쿼리를 생성합니다. DSG는 논리적 쿼리를 물리적 실행 계획으로 구체화하고 쿼리를 다양한 힌트로 변환하여 DBMS가 취약점을 검색하기 위해 여러 가지 물리적 실행 계획을 실행할 수 있도록 합니다. 조인 쿼리의 경우 조인 그래프를 와이드 테이블에 다시 매핑하여 실측 결과를 얻습니다.

패턴 설정 및 데이터 분할을 완료한 후 KQE는 패턴 다이어그램을 계획 반복 다이어그램으로 확장합니다. 각 쿼리는 하위 그래프로 표시됩니다. KQE는 기록 내(즉, 이미 탐색된 쿼리 공간 내) 쿼리 그래프의 임베딩을 위한 임베딩 기반 그래프 인덱스를 구축합니다. 직관적으로 KQE의 역할은 새로 생성된 쿼리 그래프가 기록에서 가장 가까운 이웃과 가능한 한 멀리 떨어져 있는지 확인하는 것입니다. 즉, 기존 쿼리 그래프를 반복하는 대신 새로운 쿼리 그래프를 탐색하는 것입니다. KQE는 쿼리를 생성하기 위해 적응형 랜덤 워크 방법을 사용하는 동시에 구조적 유사성을 기반으로 생성된 쿼리 그래프에 점수를 매기는 방식으로 이를 수행합니다(기록의 그래프 쿼리). .

알고리즘 1은 TQS의 핵심 아이디어를 요약한 것으로, 2, 10, 12행은 DSG이고 4, 8, 9행은 KQE입니다.

데이터 세트 와 에서 샘플링된 넓은 테이블 이 주어지면 DSG는 단일 넓은 테이블 을 3NF 호환 데이터베이스 스키마 (2행)을 형성하는 여러 테이블로 분할합니다. 패턴 은 그래프 로 볼 수 있으며, 여기서 테이블과 열은 정점이고 가장자리는 정점 간의 관계를 나타냅니다. DSG는 에서 랜덤 워크를 사용하여 쿼리의 조인 표현식을 생성합니다(10행). 실제로 조인 쿼리는 의 하위 그래프로 예상될 수 있습니다. 하위 그래프를 넓은 테이블에 다시 매핑함으로써 DSG는 이 쿼리에 대한 실측 결과를 쉽게 검색할 수 있습니다(라인 12).

KQE는 패턴 다이어그램을 계획 반복 다이어그램(라인 4)으로 확장합니다. 유사한 경로 테스트를 피하기 위해 KQE는 임베딩 기반 그래프 인덱스

를 구축하여 기존 쿼리 그래프의 임베딩을 인덱싱합니다(9행). KQE는 현재 쿼리 그래프와 기존 쿼리 그래프(8행) 간의 구조적 유사성을 기반으로 계획 반복 그래프 G의 간선 가중치 π를 업데이트합니다. KQE는 랜덤 워크 생성기를 안내하는 다음 가능한 경로의 점수를 매기므로 알 수 없는 쿼리 공간을 탐색하는 것을 선호합니다.

쿼리 의 경우 TQS는 힌트 세트 를 통해 쿼리를 변환하여 여러 가지 실제 쿼리 계획을 수행합니다(라인 11). 마지막으로 쿼리

의 결과 집합이 정답 (14행)과 비교됩니다. 일관성이 없으면 조인 최적화 취약점이 감지된 것입니다(라인 15).

DSG와 KQE에 대한 더 자세한 설명은 원문을 읽어주세요.

실험 결과

TQS는 MySQL, MariaDB, TiDB, PolarDB 등 데이터베이스 관리 시스템에서 일부 논리적 취약점을 성공적으로 발견했습니다. 이는 MySQL의 7개 취약점, MariaDB의 5개 취약점, TiDB의 5개 취약점 등 20가지 유형으로 분류됩니다. 5가지 유형이 있으며, PolarDB에는 아래 표와 같이 3가지 유형이 있습니다.

절강대학교에서 제안한 TQS의 전반적인 성능도 다른 방법에 비해 상당히 인상적이어서 여러 지표에서 훨씬 더 나은 결과를 얻었으며 각 구성 요소의 효과도 변수를 제어하여 제어하여 실험을 테스트했습니다. .

그러나 연구원들은 또한 TQS가 현재 동등 조인 쿼리에 중점을 두고 있다고 말했습니다. 그럼에도 불구하고 DSG 및 KQE 아이디어는 비동등조인의 경우에도 확장될 수 있습니다. 유일한 어려움은 쿼리 진실 결과를 생성하고 관리하는 방법입니다. 비동등조인의 경우 이러한 결과의 크기가 기하급수적으로 증가합니다. 이 부분은 앞으로도 더 많은 연구가 필요합니다.

위 내용은 하루 만에 4개 주요 데이터베이스에서 100개 이상의 취약점을 자동으로 발견한 저장대학교 연구는 SIGMOD 2023에서 최고의 논문을 수상했습니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!