Preserving Location Anonymity in Indoor Spaces
실내공간에서의 위치 익명성 보호
- 주제(키워드) Location K-Anonymity , Privacy , Hierarchical Graph , Indoor Space
- 발행기관 부산대학교
- 지도교수 이기준
- 발행년 2016
- 학위수여년월 2016. 8
- 학위명 박사
- 학과 및 전공 대학원 전기전자컴퓨터공학과-컴퓨터공학전공
- 논문 페이지 144
- 실제URI http://www.dcollection.net/handler/pusan/000000115789
- 본문언어 영어
Abstract/초록/요약
위치는 어떠한 공간에서의 점이나 영역을 식별하기 위해서 사용되며, 일반적으로 주소나 좌표를 통해 표현된다. 어떤 객체의 위치는 그 객체를 표현하는 중요한 속성으로, 단순한 좌표 이상의 의미를 가지고 있다. 특히 사람의 위치는 그 사람의 개인적인 정보를 암묵적으로 포함하고 있다. 예를 들어, 우리는 어떤 사람의 위치 정보를 통해 그 사람의 집이나 직장과 같은 정보를 파악할 수 있다. 이러한 위치는 실용적인 목적을 위해 위치기반 서비스에서 많이 활용된다. 예를 들어, 운전자들은 GPS (Global Positioning System)로 획득하는 위치를 통해서 길안내를 받을 수 있다. 무선통신과 실내측위 기술의 발전으로, 스마트 폰과 같은 이동 단말기기로 실내 위치를 획득할 수 있으며, 백화점, 컨벤션 센터, 환승역, 공항과 같이 복잡한 실내 공간이 많아지면서 위치기반 서비스의 요구가 실외뿐만 아니라 실내공간에서도 증가하고 있다. 하지만, 실내 위치기반 서비스의 실현을 위해서는 위치 프라이버시의 문제가 고려되어야 한다. 편리한 위치기반 서비스를 제공받기 위해서, 민감한 개인의 위치 정보를 위치기반 서비스 제공자에게 전송하는 것은 불가피하다. 만약에 위치 정보가 노출되면, 지능적인 공격자는 다양한 데이터베이스의 정보를 결합하여 신분을 식별하는 것이 가능해진다. 이로 인해 스토킹, 테러 위협, 개인정보 노출로 인한 금융 사기 등의 범죄에 희생자가 될 수 있다. 위치 프라이버시 보호를 위해서 많은 연구가 이루어졌으며, 그 중에서 K -익명화는 적어도 K -1명의 다른 사용자의 위치를 포함하는 은폐영역으로 질의자의 위치를 은닉시키는 방법이다. 하지만 실내공간과 실외공간의 특성 차이 때문에, 기존의 K -익명화 방법을 실내공간에 곧바로 적용하는 것은 어려움이 있다. 먼저 실내공간에서의 거리에 대한 정의가 실외공간이나 도로네트워크의 거리와 다르다. 그리고 실외공간에서 사용하는 익명화 공간영역의 형태가 실내공간의 지역성을 보장하지 못한다. 기존 연구의 한계를 극복하기 위해서, 본 논문에서는 실내 위치 K -익명성의 개념에 대해 소개하고, 실내공간에서 적절한 익명화영역에 대한 요구사항을 정리한다. 본 논문의 범위를 다음과 같이 지정한다. 질의 타입: 공간질의의 타입에 따라 익명화에서 중요한 요소들이 다르게 정의될 수 있다. 본 논문에서는 실내공간에서 실내거리를 적용한 r -영역 질의와 k -최근접 질의를 다룬다. 질의의 대상은 정적, 동적 객체 둘 다 될 수 있다. 보호 대상: 본 논문에서 보호하려는 대상은 질의자의 위치 익명성이고, 이를 통해 질의자의 신원이 드러나지 않도록 하는 것이다. 공간은 시멘틱을 포함할 수 있기 때문에, 질의자의 문맥 정보가 노출될 수 있는데, 본 논문에서는 l -다양성을 통해서 질의자의 위치로부터 문맥정보를 보호한다. 익명화 공간의 범위: 실내 위치기반서비스 사용자가 건물과 같은 실내공간에 대한 질의를 요청할 경우, 이미 사용자가 그 공간에 흥미를 가지고 있다는 것이 드러나게 된다. 본 논문에서는 건물의 단위가 아닌 방 단위의 위치보호 방법론에 대해 다룬다. 익명화 담당자: 익명화는 중앙집중방식과 분산방식으로 나뉠 수 있는데, 본 논문은 중앙집중 방식에 대해 다룬다. 따라서 클라이언트는 다른 사용자의 위치 정보를 알 수 없고, 익명화와 관련된 어떠한 프로그램 로직을 포함하고 있지 않다. 공격 모델: 본 논문은 center-of-ASR 공격과 replay attacks 공격 모델을 적용한다. center-of-ASR은 익명화 영역의 중앙에 질의자가 있을 것이라는 가정으로 질의자를 찾는 공격 방법이다. replay attack은 익명화 공간에 있는 모든 위치에서 동일한 알고리즘을 반복적으로 수행하여, 질의의 진원지를 찾는 공격 방식이다. 익명화의 중요한 요구사항은 공격으로부터 안전하고 효율적으로 질의를 처리할 수 있는 익명화 영역을 결정하는 것이다. 효율성은 실내공간의 특성에 따라 달라지게 되는데, 본 논문에서는 실내공간의 특성을 반영한 계층그래프를 이용하여 익명화 영역을 결정하는 세 가지 방법을 제안한다. 익명화는 질의자의 위치를 숨기는 과정으로, 실제 질의는 서비스 제공자가 처리하게 된다. 질의의 형태가 바뀌기 때문에, 그에 따른 질의처리 방법론이 필요하다. 서비스 제공자 측면에서의 익명화된 영역질의와 최근접질의를 처리하는 방법에 대해 제안한다. 본 논문에서 계층 그래프는 K -익명성을 위해 중요한 자료 구조이기 때문에, 그에 따른 계층 그래프 생성방법을 소개한다. 또한 질의처리 성능과 공격에 대한 탄성력의 실험을 통해 본 논문에서 제안하는 방법들을 검증한다.
more목차
1 Introduction 1
1.1 Backgrounds and Motivation 2
1.2 Approaches 6
1.3 Outlines 9
2 Related Work 10
2.1 Classification of Protecting Location Privacy 10
2.2 K-anonymity 12
2.3 Location K-anonymity 13
2.3.1 System Model 14
2.3.2 Location K-anonymity in Euclidean Space 15
2.3.3 Location K-anonymity in Road Networks 17
2.4 Motivations 18
2.4.1 Difference in the Distance Metric 18
2.4.2 Improper form of ASR 21
2.4.3 Query Processing for Indoor Location K-anonymity 22
3 Preliminaries 23
3.1 System Model 23
3.2 Indoor Space Modeling 24
3.2.1 Cellular Space 25
3.2.2 Hierarchical Graph 25
3.2.3 Distance in Indoor Spaces 29
3.3 Cellular Space and Anonymization in Indoor Spaces 33
3.4 Considerations for ASR Extension 34
3.4.1 Resilience against attacks 34
3.4.2 Efficiency of Query Processing 35
4 ASR Determination 37
4.1 K-Anonymity using Hierarchical Graph 37
4.2 K-Anonymity using an H-Graph by Random Selection 39
4.3 K-Anonymity on Cell Ordering using an H-Graph 40
4.3.1 Organization of Buckets 42
4.3.2 Indexing for Moving Objects in Buckets 43
4.3.3 Considerations for Advanced Organization of Buckets 45
5 Query Processing 48
5.1 Composite Index for Indoor Objects 48
5.2 r-range Query 49
5.3 k-NN Query 51
6 H-Graph for K-Anonymization 55
6.1 Factors of K-Anonymization 55
6.2 Generating Base Graph 57
6.3 Algorithm of Generating Graph 58
7 Linear Mapping in Indoor Spaces 64
7.1 Considerations for Linear Mapping 64
7.2 Indoor Space Partitioning and Hierarchy 65
7.3 Analysis of Hilbert Curve 67
7.4 Linear Mapping using H-Graph 69
8 Experimental Analysis 73
8.1 Experimental Setup 74
8.2 Characteristics of Hierarchical Graphs 77
8.3 Analysis of Resilience against Attacks 80
8.4 Analysis of K-Anonymization at the Anonymizer 83
8.5 Analysis of Query Processing with the ASR at the LSP 91
8.5.1 Comparison of Number of Candidates 91
8.5.2 Comparison of Response Time 92
8.6 Analysis of Linear Mapping 97
9 Conclusion 105
9.1 Summary 105
9.2 Discussion 105
9.3 Future Work 107
9.3.1 Limitation of Our Work 107
9.3.2 Open Issues 108
References 110
Appendix A 120
Appendix B 121
Appendix C 124
Appendix D 126
Appendix E 135
