실시간 스트림 데이터를 위한 새로운 익명화 알고리즘 제안 = Proposal of a New Anonymization

국문 초록 (Abstract)

실시간 스트림 데이터라 함은 실시간 범죄신고정보, 온라인 판매거래정보, 병원 내 환자 모니터링 장치 등 각종 PoC(Point of Care, 현장 진료형 의료장비)들로부터 실시간으로 수집되는 개인생체신호 등의 데이터를 말한다. 우리는 이러한 실시간 수집 스트림 데이터에서의 프라이버시 보호를 위한 새로운 익명처리 알고리즘을 제안하고자 한다. 제안 알고리즘은 기존 Ugur와 Osman이 제안한 UBDSA 알고리즘보다 크게 4가지 측면에서 성능을 개선하였다. 첫째, 일반화 트리를 형성한 다음 정보손실을 미리 측정할 수 있도록 사전 수행과정(Precompute)을 두었다. 둘째, 각 트랜잭션 데이터(레코드)가 입력될 때마다 슬라이싱을 통하여 준식별자 컬럼들과 아닌 컬럼들을 분리하여 각각 저장하였으며, 아울러 게시전 조합(combine)을 위하여 분리시 분리된 각 슬라이스에 일련번호를 붙이도록 하였다. 즉, 각 트랜잭션 별로 클러스터링시 준식별자 컬럼들만 저장하여 일반화함으로써 저장공간을 줄이고 계산 성능을 개선하였으며, 특히 이것은 컬럼수가 많거나 혹은 대용량 데이터에 대해 보다 효율적이다. 셋째, 클러스터 할당(AssignCluster) 단계에서 성능을 아래와 같이 개선하였다. 먼저 지연 임계값(입력 후 게시될때 까지의 최대 허용 가능 트랜잭션 레코드 수)이하 초기 클러스터 할당 과정에서부터 기존 알고리즘과 달리 각각 별도의 클러스터에 배정하지 않고 정보손실을 고려하여 클러스터링을 수행하였다. 끝으로 일반화 및 게시(Publish 단계)에서 성능을 개선하였다. 기존과 달리 클러스터 내 튜플의수가 2k 이상인 클러스터에 대해 분할 과정을 미수행하며 기존 주장인 데이터 품질 개선과는 달리 굳이 분할을 하지 않더라도 그 자체로도 데이터 품질이 좋을 수도 있으며, 안전성이 보다 높고 과정을 수행하지 않음으로 인해 성능도 향상된다. 또한 기존 UBDSA 알고리즘과 달리 클러스터 내 튜플의수가 k보다 적은 경우 이동 가능한 타 클러스터를 탐색 후 가능 클러스터를 찾아 이를 배정하는 과정에서 랜덤 배정이 아닌 최소거리 기반 배정을 수행하였다. 이는 기존 주장인 정보유출로 인한 반대 공격을 피하는 것과 달리 최소 k값이 보장될 경우 유용성 차원에서 최소거리인 클러스터로 배정이 타당하다. 그리고 앞서 클러스터 내 튜플의 수가 k보다 적은 경우 이동 가능한 타 클러스터를 탐색 후 가능 클러스터를 못찾았거나 혹은 익명화되지않은 클러스터 내 튜플수가 중앙값 클러스터 크기보다 작은 경우 기존 삭제 혹은 최상위 일반화 대신 제안 알고리즘은 삭제를 수행함으로서 수행 시간을 줄일 수 있다.

다국어 초록 (Multilingual Abstract)

Real-time stream data refers to data which collected in real time such as personal vital signs information collected from various PoCs (Point of Care, point-of-care medical equipment) in hospitals, real-time crime report information, and online sales transaction. We propose a new anonymization algorithm for privacy protection in these real-time collected stream data. The proposed algorithm significantly improved performance in four aspects compared to the UBDSA algorithm proposed by Ugur and Osman. First, after forming a generalization tree, precompute was performed to measure information loss in advance. Second, whenever each transaction data (record) is entered, quasi-identifier columns and non-identifier columns are separated and stored through slicing, and serial numbers are attached to each slice separated at the time of separation for combine before publishing, That is, when clustering for each transaction, only quasi-identifier columns are stored and generalized to reduce storage space and improve calculation performance. In particular, it is more efficient for large numbers of columns or large-capacity data. Third, the performance in the cluster assignment (AssignCluster) step was improved as follows. First, from the initial cluster assignment process below the delay threshold (the maximum allowable number of transaction records from input to publishing), clustering was performed in consideration of information loss, rather than assigning to separate clusters, unlike existing algorithms. Finally, performance was improved in generalization and publishing (Publish stage). First, after forming a generalization tree, precompute was performed to measure information loss in advance. Second, whenever each transaction data (record) is entered, quasi-identifier columns and non-identifier columns are separated and stored through slicing, and serial numbers are attached to each slice separated at the time of separation for combine before publishing, That is, when clustering for each transaction, only quasi-identifier columns are stored and generalized to reduce storage space and improve calculation performance. In particular, it is more efficient for large numbers of columns or large-capacity data. Third, the performance in the cluster assignment (AssignCluster) step was improved as follows. First, from the initial cluster assignment process below the delay threshold (the maximum allowable number of transaction records from input to publishing), clustering was performed in consideration of information loss, rather than assigning to separate clusters, unlike existing UBDSA algorithm. Finally, performance was improved in generalization and publishing (Publish stage). The partitioning process is not performed for clusters with more than 2k tuples in the cluster, and unlike the existing data quality improvement claims, data quality can be good without partitioning and safety is higher. It improves performance by not running the process. If the number of tuples in a cluster is less than k, after searching for other movable clusters, in the process of searching and assigning, possible clusters are found and assigned based on the minimum distance rather than random assignment. Contrary to the previous argument, if the minimum value of k is guaranteed to avoid counterattack due to information leakage, it is reasonable to assign it to the cluster with the minimum distance in terms of usefulness. And if the number of tuples in a cluster is less than k previously, if no possible cluster is found after searching for other movable clusters, or if the number of tuples in a non-anonymized cluster is smaller than the medium-sized cluster, then we can reduce execution time because we choose only deletion rather than existing generalization of the top-level or deletion.

참고문헌 (Reference)

• 1 A. Machanavajjhala, "l-diversity : Privacy beyond k-anonymity" 1 (1): 3-14, 2007
• 2 L. Sweeney, "k-anonymity: A model for protecting privacy" 10 (10): 557-570, 2002
• 3 "https://www.questrade.com/pricing/self-directed-commissions-plans-fees"
• 4 "https://www.hl7.org/fhir/"
• 5 "https://www.hl7.org/"
• 6 "https://kosis.kr/index/index.do"
• 7 W. Wang, "Privacy protection on sliding window of data streams" 213-221, 2007
• 8 K. Guo, "Fast clustering-based anonymization approaches with time constraints for data streams" 46 : 95-108, 2013
• 9 H. Zakerzadeh, "Data privacy management and autonomous spontaneous security" Springer 36-50, 2011
• 10 J. Cao, "Castle : continuously anonymizing data streams" 8 (8): 337352-, 2011
• 11 J. Li, "Anonymizing streaming data for privacy protection" 1367-1369, 2008
• 12 Ugur Sopaoglu, "A utility based approach for data stream anonymization" 54 : 605-631, 2020
• 13 S. Kim, "A framework to preserve the privacy of electronic health data streams" 50 : 95-106, 2014