Automaton Segmentation: A New Approach to PreservePrivacy in XML Information BrokeringFengjun Li, Bo Luo, Peng Liu, Dongwon Lee, and Chao-Hsien ChuThe Pennsylvania State UniversityUniversity Park, PA 16802, USA{fengjun, bluo, pxl20, dongwon, chc4}@psu.eduABSTRACTA Distributed Information Brokering System (DIBS) is apeer-to-peer overlay network that comprises diverse dataservers and brokering components helping client queries lo-cate the data server(s). Many existing information broker-ing systems adopt server side access control deployment andhonest assumptions on brokers. However, little attentionhas been drawn on privacy of data and metadata stored andexchanged within DIBS. In this paper, we address privacy-preserving information sharing via on-demand informationaccess. We propose a flexible and scalable system using abroker-coordinator overlay network. Through an innovativeautomaton segmentation scheme, distributed access controlenforcement, and query segment encryption, our system in-tegrates security enforcement and query forwarding whilepreserving system-wide privacy. We present the automatonsegmentation approach, analyze privacy preservation in de-tails, and finally examine the end-to-end performance andscalability through experiments and analysis.Categories and Subject DescriptorsK.4.1 [COMPUTERS AND SOCIETY]: Public Pol-icy Issues—privacy; K.6.5 [MANAGEMENT OF COM-PUTING AND INFORMATION SYSTEMS]: Secu-rity and ProtectionGeneral TermsSecurityKeywordsPrivacy, XML, Access Control1. INTRODUCTIONIn a federated information system with diverse partici-pants (from different organizations) such as data producers,data consumers, or both, the need of cross-organizational in-formation sharing naturally arises. However, different typesPermission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.CCS’07, October 29–November 2, 2007, Alexandria, Virginia, USA.Copyright 2007 ACM 978-1-59593-703-2/07/0011 ...$5.00.1357624Data ServerBrokerCoordinatorUserUserUserUser UserUserUserUserUserUserUserUserUserUserUserUserUserUserUserUserUserDataServerCoordinatorTreeBrokerSuperSitePhase 1Phase 2Phase 3Phase 4Broker-CoordinatorNetworkSuper NodeData ServerData ServerData ServerData ServerBroker-Coordinator Network12810769534Figure 1: System architecture of a distributed infor-mation brokering systemof applications often need different forms of information shar-ing. In particular, while some applications (e.g., stock priceupdating) would need a publish-subscribe framework [3, 6],the on-demand information access is more suitable for otherapplications. Examples include cases like querying for prod-ucts (parts) from manufactures and contractors network orproviding emergency health care services to visitors (or tourists)whose medical records are not in local hospitals. Considerthe following motivating example.Example 1. Let us consider a medicare network scenario.Each organization (e.g., hospital) participates as a data sourcethat holds its own patient database. Since the records arehighly sensitive and private, intensive privacy and securityenforcement is desired. Diverse users (e.g., doctors, as-sistants, pharmacists, and administrators) are to access localor remote patient data according to certain access controlpolicies. Furthermore, users who ask queries from their ownterminals do not have to have prior knowledge of data distri-bution. For instance, when a doctor wants to retrieve all thehistorical records of a patient, her query may be forwardedto all data sources that hold related information. However,the user does (and should) not need to known where thedata comes from. 2When N parties need to share data, as shown in Exam-ple 1, “pouring” all data into a centralized repository man-aged by a third party may lead to legal/political hurdlesand trust/privacy concerns. In such scenarios, a peer-to-peer information sharing framework can be desirable. In itssimplest form, we may establish two symmetric client-serverrelationships between every pair of parties, but having 2Nrelationships is not scalable. To achieve better scalability,peer-to-peer overlay networks have been proposed to includenot only the data servers of N parties but also a set of infor-mation brokering components helping client queries lo catethe right data server(s) [11, 12, 13]. In this paper, such a dis-tributed on-demand information access system is referred toas Distributed Information Brokering System (DIBS). Fig-ure 1 shows an example DIBS (to be elaborated in Sec-tion 3.4). When data are owned, scattered, and managedby multiple parties in DIBS, various privacy concerns arise.Consider the following example.Example 2. Continuing from Example 1, suppose that Anneis in ER and all patient data are stored and managed in XMLformat (as opposed to in relational records). If a doctor’sXML query, “/provider/.../patient[name()=‘Anne’]/symptom[cancer()=‘blood’]//*”, is disclosed, then peo-ple may guess that Anne has a cancer. Similarly, Anne maynot wish to reveal that she is now in Los Angeles underemergency health care but her health records are stored inMt. Sinai Hospital of New York, since people may guessthat she has cancer related problem if they know that herrecords are from the hospital renowned for its blood cancertreatment. That is, a medicare DIBS needs to protect notonly confidentiality of patient data, but also privacy of suchsensitive information as “who asks what queries” or “wheredata comes from”. 2Despite its importance, to our best knowledge, none ofexisting DIBS work is designed with user and data privacyin mind. To satisfy such privacy protection requirements,therefore, we propose a novel DIBS, named as Privacy Pre-serving Information Brokering system (PPIB). As shown inFigure 1, PPIB contains a broker-coordinator overlay net-work, in which the brokers are responsible for forwardinguser queries to coordinators concatenated in tree structurewhile preserving privacy. The coordinators, each holding asegment of access control automaton and routing guidelines,are mainly responsible for access control and query routing.PPIB takes an innovative automaton