Report Documentation Page Form Approved OMB No. 0704-0188 Public reporting burden for the collection of information is estimated to average 1 hour per response, including the time for reviewing instructions, searching existing data sources, gathering and maintaining the data needed, and completing and reviewing the collection of information. Send comments regarding this burden estimate or any other aspect of this collection of information, including suggestions for reducing this burden, to Washington Headquarters Services, Directorate for Information Operations and Reports, 1215 Jefferson Davis Highway, Suite 1204, Arlington VA 22202-4302. Respondents should be aware that notwithstanding any other provision of law, no person shall be subject to a penalty for failing to comply with a collection of information if it does not display a currently valid OMB control number. 1. REPORT DATE 3. DATES COVERED 2015 2. REPORT TYPE 00-00-2015 to 00-00-2015 4. TITLE AND SUBTITLE 5a. CONTRACT NUMBER 20,000 In League Under the Sea: Anonymous Communication, Trust, 5b. GRANT NUMBER MLATs, and Undersea Cables 5c. PROGRAM ELEMENT NUMBER 6. AUTHOR(S) 5d. PROJECT NUMBER 5e. TASK NUMBER 5f. WORK UNIT NUMBER 7. PERFORMING ORGANIZATION NAME(S) AND ADDRESS(ES) 8. PERFORMING ORGANIZATION Naval Research Laboratory ,Washington,DC,20375 REPORT NUMBER 9. SPONSORING/MONITORING AGENCY NAME(S) AND ADDRESS(ES) 10. SPONSOR/MONITOR’S ACRONYM(S) 11. SPONSOR/MONITOR’S REPORT NUMBER(S) 12. DISTRIBUTION/AVAILABILITY STATEMENT Approved for public release; distribution unlimited 13. SUPPLEMENTARY NOTES 14. ABSTRACT Motivated by the effectiveness of correlation attacks against Tor, the censorship arms race, and observations of malicious relays in Tor, we propose that Tor users capture their trust in network elements using probability distributions over the sets of elements observed by network adversaries. We present a modular system that allows users to efficiently and conveniently create such distributions and use them to improve their security. To illustrate this system, we present two novel types of adversaries. First, we study a powerful, pervasive adversary that can compromise an unknown number of Autonomous System organizations, Internet Exchange Point organizations, and Tor relay families. Second we initiate the study of how an adversary might use Mutual Legal Assistance Treaties (MLATs) to enact surveillance. As part of this, we identify submarine cables as a potential subject of trust and incorporate data about these into our MLAT analysis by using them as a proxy for adversary power. Finally, we present preliminary experimental results that show the potential for our trust framework to be used by Tor clients and services to improve security. 15. SUBJECT TERMS 16. SECURITY CLASSIFICATION OF: 17. LIMITATION OF 18. NUMBER 19a. NAME OF ABSTRACT OF PAGES RESPONSIBLE PERSON a. REPORT b. ABSTRACT c. THIS PAGE Same as 21 unclassified unclassified unclassified Report (SAR) Standard Form 298 (Rev. 8-98) Prescribed by ANSI Std Z39-18 20,000InLeagueUndertheSea 5 and(iii)combinesthisworldwiththeuser’strustbeliefs canbeusedtodescribeTorrelaysandthattheyassume to produce a Bayesian Belief Network (BBN; see, e.g., each relay has an independent chance of compromise. [14]) representing a distribution on the sets of network The framework we present here represents a significant elementsthatanadversarymightcompromise.Thesys- advance in that it includes a diverse set of network el- tem we describe is designed to produce a distribution ements, including elements such as IP routers or IXPs on the sets of network locations that might be com- that exist only on the paths between Tor relays. We al- promised by a single adversary. In the case of multiple, low new types of network elements to be added in nat- non-colluding adversaries, multiple distributions could ural ways. Another contribution of our system is that be produced. it can be used to represent arbitrary probability distri- We illustrate how this system might work by intro- butions over the sets of network elements, and yet we ducingtwonoveltypesofadversaries.First,weconsider showhowthemostlikelydistributionscanbeefficiently a powerful, pervasive adversary called The Man that represented and used. is potentially observing any independent group of of Thebodyofthispaperprovidesahigh-levelviewof AutonomousSystems(ASes),InternetExchangePoints our system, starting with an overview of its operation (IXPs),orrelayfamilies.Theuserisuncertainaboutex- and what the system provides in Sections 2 and 3. We actlywhatthisadversarycanobserve,butshehassome describeinSection4howthesystem-providedinforma- information about the risk at different locations. This tion is combined with user beliefs to produce a BBN. adversary can be seen as a generalization of previous We discuss some issues related to users’ trust beliefs threatmodelsinwhichanadversarymightcompromise in Section 5. We present The Man in Section 6. In Sec- relays in the same /16 subnet or family, or in which an tion7,wediscussMLATsandanalyzetheirimplications individual AS or IXP might be malicious. for adversary capabilities; the randomized construction Second, we initiate the study of the effects of Mu- of hypothetical adversaries for that analysis is guided tualLegalAssistanceTreaties(MLATs)onthereachof by countries’ connections to submarine cables. We then adversaries;wealsoidentifysubmarinecablesaspoten- present,inSection8,experimentalresultsfromourtrust tially important subjects of (dis)trust and incorporate system. We close in Section 9 with a discussion of the data about these into our analysis. Here, we demon- implications of the work presented here and a sketch of strate the use of an MLAT database to inform analysis ongoing and future work. As noted throughout, some offirst–lastcompromise.Therandomizedstate-levelad- additional details are provided in the appendices. versariesthatweconstructforthismakeuseofdataon submarine cables, opening up that avenue of study in connection with anonymity networks. We use existing 2 System Overview Tor traceroute data to give an initial understanding of howMLATsmayexpandthecapabilitiesofadversaries. Wesurveyoursystem,whichislargelymodular.Thisal- In addition, we present proof-of-concept experi- lowsittobeextendedasnewtypesoftrustinformation mentsthatshowhowourtrustsystemmightbeusedby areidentifiedasimportant,etc.Thesystemcomeswith client or servers to improve their security. We suppose an ontology that describes types of network elements that users choose paths and servers choose locations to (e.g., AS, link, and relay-operator types), the relation- minimizetheriskoffirst–lastcorrelationattacksbyThe ships between them that capture the effects of compro- Man. The results show that users and services can em- mise by an adversary, and attributes of these things. ploy our system to improve their security. While we provide an ontology, this may be replaced by Themainpartofourmodularsystemwasdescribed anotherontologyasothertypesofthreatsareidentified. inanunpublishedpaper[19].Theversionpresentedhere Section 3.1 describes the requirements for replacement explicitly accounts for MLATs in the way that we use ontologies.Roughlyspeaking,theontologyidentifiesthe them,amodificationthatdemonstratestheflexibilityof typesofentitiesforwhichthesystemcanautomatically our system. Our use of the MLAT and cable databases handle user beliefs when constructing the Bayesian Be- andouranalysisoftheeffectsofMLATsonthereachof lief Network (BBN) for the user. A user may express adversaries are also new since that preliminary version beliefsaboutothertypesofentities,butshewouldneed of this work. to provide additional information about how those en- Other work [20, 21] has considered the use of trust tities relate to entities whose types are in the ontology. to improve security in Tor. The models of trust in this previousworkhavethemajorlimitationsthattheyonly Unauthenticated Download Date | 4/21/15 5:21 PM 20,000InLeagueUndertheSea 6 Theontologyisprovidedtotheuserinordertofacilitate specification(s) must describe not only the syntax for this. the user but also (i) how her structural beliefs will be In general, we expect that the system will provide used in modifying the system-generated world and (ii) information about network relationships, such as which howherotherbeliefswillbeusedtotranslatetheedited ASesandIXPsareonacertainvirtuallinkorwhichTor world into a BBN. relays are in a given relay family. We generally expect Once constructed, the BBN can be used, e.g., to the user to provide information about human–network provide samples from the distribution of the Tor re- relationships such as which individual runs a particular laysandTor“virtuallinks”(transport-layerconnections relay. Note that this means the user might need to pro- withTorrelays)thatareobservedbytheadversary.The vide this type of information in order to make some of motivatingapplicationistousethesesamplestoinform herbeliefsusable.Forexample,ifshehasabeliefabout more secure path selection in Tor. the trustworthiness of a relay operator, she would need to tell the system which relays that operator runs in order for the trustworthiness belief to be incorporated 2.1 Construction sequence into the BBN. Using the ontology and various published informa- An overview of the system’s actions is as follows. The tionaboutthenetwork,thesystemcreatesapreliminary various attributes and beliefs mentioned here are de- “world” populated by real-world instances of the ontol- scribed in detail in the following sections. ogy types (e.g., specific ASes and network operators). 1. World generation from ontology: WI R T The world also includes relationship instances that re- – As described in Section 3.3, the system generates flectwhichparticulartypeinstancesarerelatedinways a preliminary view of the world based on the on- suggested by the ontology. User-provided information tology and its data sources. We denote the result may include revisions to this system-generated world, by WI. R T including the addition of types not included in the pro- – This includes system attributes. videdontologyandinstancesofbothontology-provided 2. Augmenting the types with the user’s types: WI R T0 and user-added types. The user may also enrich the in- – The user may provide additional types (as a pre- formationabouttheeffectsofcompromise(adding,e.g., lude to adding instances of those types to the budget constraints or some correlations). world). We use WI to denote the augmentation R T0 The user expresses beliefs about the potential for of WI by adding the user’s types. R T compromise of various network entities; these beliefs 3. Adding user-specified instances of types (ontology may refer to specific network entities or to entities that and user-provided): WI0 R T0 satisfysomecondition,eveniftheusermaynotbeable – The user may add instances of any of the types to effectively determine which entities satisfy the con- in WI . We use WI0 to denote the augmenta- R T0 R T0 dition.Thisuser-providedinformationisused,together tion of WI by adding these new instances and R T0 with the edited world, to create a Bayesian Belief Net- removing any that the user wishes to omit. work (BBN) that encodes the probability distribution 4. Adding user-specified relationships (between in- on the adversary’s location that arises from the user’s stances in WI0): WI0 R T0 R0 T0 trust beliefs. A user may express a belief that refers to – Theusermayspecifyadditionalparent/childrela- an entity or class of entities whose type is in the given tionships beyond those included in WI0. In par- R T0 ontology.Forsuchbeliefs,thesystemwillbeabletoau- ticular, any new instances that she added in the tomaticallyincorporatethosebeliefsintotheBBNthat previous step will not be related to any other in- the system constructs. A user may also express beliefs stancesintheworldunlesssheexplicitlyaddssuch aboutentitieswhosetypesarenotincludedintheontol- relationshipsinthisstep.Weuse WI0 todenote R0 T0 ogy.Ifshedoesso,shewouldneedtoprovidethesystem the augmentation of WI0 by adding these new R T0 withinformationabouthowthoseentitiesshouldbeput relationships and by removing any that the user into the BBN that the system constructs. wishes to omit. The system and the user need to agree on the lan- 5. Editsystem-providedattributes(notbudgetsorcom- guage(s) in which she will express her beliefs. Different promise effectiveness). users (or, more likely, different organizations that want 6. Add new user-provided attributes. to provide collections of beliefs) may find different lan- 7. Add budgets. guagesmostnaturalforexpressingbeliefs.Thelanguage Unauthenticated Download Date | 4/21/15 5:21 PM 20,000InLeagueUndertheSea 7 8. Addcompromiseeffectiveness(ifvaluesarenotgiven, obtain information but the ontology designer is able this defaults to a value provided by the ontology; toaccountforinstancesoftheedge/typeintheBBN- for relationships of types not given in the ontology, construction procedure. we will use a default value unless the user specifies – A collection A of attributes. Each attribute includes somethingwhenprovidingtherelationshipinstance). a name, a data type, a source (either “system” or 9. Produce BBN. “user”).EachelementofT ∪E maybeassignedmul- – In this overview, this process is treated as a black tiple boolean combinations of attributes; each com- box. In practice, it involves many steps that de- bination is labeled with either “required” or “op- pend on the belief language used. The procedure tional.”1 forthebelieflanguagedescribedinSec.4.2ispre- Otherontologiesmaymodularlyreplacetheonede- sented in detail in Sec. 4.3. scribed here if they satisfy the assumptions described above. 3 Ontology and World 3.2 Our ontology Beforepresentingtheontologythatweuseinthiswork, Figure 1 shows the elements of our ontology. Rounded we describe our general requirements for ontologies in rectangles are types; instances of these will be factor thisframework.Thisallowsourontologytobereplaced variables in the BBN produced by the system. Ovals with an updated version satisfying these requirements. are output types: Tor relays and (virtual) links be- tweenclientsandguardsandbetweenexitsanddestina- tions. Cylinders are attributes, whose interpretation is 3.1 General requirements for ontologies described below. With the exception of Relay Software and Physical Location, which the system provides but We assume that any ontology used in our system has the user may modify, these attributes are provided by the following properties: the user. The user may also provide new attributes. – IthasacollectionT oftypes.Weusetheontologyto Directededgesshowexpectedrelationshipsbetween describe relationships between the types in the on- types. For example, the edge from the “AS” type to tology. the“Router/switch”typeindicatesthatweexpectthat – AcollectionE of(directed)edgesbetweentypes(with the compromise of an AS will likely contribute to the E ∩T = ∅). The edges are used to specify relation- compromise of one or more routers and switches. This ships;ifthereisanedgefromT toT intheontology, 1 2 edge is dashed in Fig. 1 to reflect the label “user,” i.e., thenthecompromiseofanetworkelementoftypeT 1 we currently expect the user to identify which AS con- has the potential to affect the compromise of a net- trols a particular router or switch if that effect is to be work element of type T . 2 incorporated into the BBN construction. Other dashed – Viewed as a directed graph, (T,E) is a DAG. edgesandtheunfilledtypes/attributesarealsoelements – AdistinguishedsetofT calledtheoutput types.This that we expect to be provided by the user. Solid edges is for convenience; these are the types of instances andfilled-intypescorrespondtoelementsandattributes that we expect will be sampled for further use. We whose label is “system;” we expect the system provide generally expect the output types to be exactly the information about these. types in the ontology that have no outgoing edges. – Each element of T ∪E has a label that is either “sys- tem” or “user.” For an edge e from type T to type 1 T , if either T or T has the label “user,” then e 1 Intherestofthispaper,weassumethateachcombinationis 2 1 2 must also have the label “user.” These labels will be justasingle“optional”attributewithoutanyconnectives.The semanticsofindividualattributesdependonthetranslationpro- used to indicate the default source of instances of cedurethatproducestheBBN.Weexpectthatabooleancombi- each type. (However, the user may always override nationofattributeswillbeinterpretedaspossiblecombinations system-provided information.) ofattributesthatthetranslationprocedurecanhandle;forex- Types or edges with the label “user” might be nat- ample,itmightbeabletoprocesseitherapairofintegersora ural to include in an ontology when the type/edge singlerealvalue.Richerapplicationsofthe“optional”and“re- quired”labelsmightbeallowedaswell,althoughwedonotneed is something about which thesystem cannotreliably themhere. Unauthenticated Download Date | 4/21/15 5:21 PM 20,000InLeagueUndertheSea 8 Legal   Type   AHribute   System-­‐generated   Jurisdic6on   Region   Compromise   Budget   MLAT   Effec6veness   Type   AHribute   User-­‐provided   Output  type   Legal   System-­‐generated  edge   Jurisdic6on   User-­‐provided  edge   AS  Org.   Corpora6on   IXP  Org.   Relay   Hos6ng  Service   AS   SoGware   Connec6on   Router/ Relay   Type   Switch  Kind   Hardware   Relay  Family   Physical   Loca6on   Relay  Operator   IXP   Physical   Router/Switch/ Connec6on   etc.   Virtual   Tor  Relay   Link   Fig.1.Graphicaldepictionofthesystem’sontology 3.2.1 User-provided types source to which the user has access) may be added as instances of this type. The types and relationships that are provided by the Physical connection Particular physical connec- system in constructing the preliminary world are de- tions, such as a specific cable or wireless link, may scribed in Section 3.3. We describe the others here; in- be known and of interest. stances of these are added by the user in ways specified (Physical connection, Virtual link) If a virtual below. link is known to use a specific physical connection, Hosting Service (and incident edges) Hosting then that can be reflected in a relationship between services that might be used to host Tor relays. If the two. a service hosts a particular relay, there would be a relationship instance from the service to the relay. If a service is known to be under control of a partic- 3.2.2 Attributes ular legal jurisdiction or company, the appropriate incoming relationship instance can be added. Theattributesinourontologyaredepictedbycylinders Corporation (and incident edges) Corporate con- in Fig. 1. The two at the box in the top right can be trol of various network elements may be known. A applied to all non-output type instances, so we do not corporation that is known may be added as an in- explicitly show all of the types to which they can be stance of this type. If the corporation is known to applied. be subject to a particular legal jurisdiction, then a System-generated attributes These include relay- relationship edge from that jurisdiction to the cor- softwaretypeandrouter/switchtype.Usersmayedit poration can be added. Similarly, hosting services, these, e.g., to provide additional information. ASes, and IXPs that a corporation controls may be Connection type This is an attribute of physical- soindicateviatheappropriaterelationshipinstances. connection instances. It is represented as a string Router/switch/etc. This corresponds to a physical that describes the type of connection (e.g., routerorswitch.Wedonotattempttoidentifythese "submarine cable", "buried cable", or "wireless automatically, but ones known to the user (or a connection"). A user would express beliefs about connection types; if the type of a connection is cov- Unauthenticated Download Date | 4/21/15 5:21 PM 20,000InLeagueUndertheSea 9 eredbytheuser’sbeliefs,thentheprobabilityofcom- p=10−4), it might make a mistake in the configura- promisewouldbeaffectedinawaydeterminedbythe tionfileforacertainroutermodelthatwouldprevent belief in question. it from compromising routers of that model that are Budget Thisattribute,whichissuppliedbytheuserat not otherwise compromised. However, if such a mis- heroption,maybeappliedtoanynon-outputtypein- take is not made, then the AS will compromise all stance. There are two variants. Both are represented routers of that model; this is in contrast to the ef- asanintegerkandanothervalue.Inthefirstvariant, fects of budget beliefs. the other value is a type; in the second variant, the Router/Switch Kind This is an attribute of other value is the string "all". Multiple instances routers/switchesandisrepresentedasasetofstrings. of this attribute may be applied to a single type in- We expect the user to use this to describe aspects stance as long as they have distinct second values; if of routers/switches that she might know about and oneoftheseisthesecondvariant,thenallotherswill want to use in her trust beliefs, e.g., the model be ignored. This allows the user to express the belief number or firmware version of specific routers and that,ifthetypeinstanceiscompromised,thenitsre- switches. sourcesallowittocompromisekofitschildren.Inthe Relay Hardware This is an attribute of relays and first variant of this attribute, the instance may com- is represented in the same way as the router/switch promise k of its children of the specified type (and kind. Also analogously to that attribute, we expect perhaps k0 of its children of a different type, if so that the user would use this to describe aspects of specified by a different belief). In the second variant relay hardware that she might know about and po- of this attribute, the instance may compromise k of tentially use in her trust beliefs. its children across all types.2 Asdiscussedbelow,wemustapproximatetheeffects of resource constraints so that the BBN can be effi- 3.3 System-generated world ciently sampled. Region This is an attribute of legal jurisdiction. It is The system provides users with a world consisting of representedasabooleanpredicateongeographicco- type instances and relationship instances that are con- ordinates. sistent with the types and relationships specified in the Compromise effectiveness This attribute is syntac- ontology. Formally, a world is a DAG in which each tically similar to the budget attribute. It is supplied vertex is a type instance, each edge is a relationship by the user at her option for instances of any non- instance, and an attribute function assigns each ver- output type, and there are effectively two variants. tex a vector of attributes. A type instance represents This is represented as a probability p ∈ [0,1] and a a real-world object of the specified type. For example, boolean predicate on type instances; we distinguish “AS3356” is a type instance of the AS type, and “Level non-trivialpredicatesfromthealways-truepredicate 3 Communications” is a type instance of the AS Orga- >.Multipleinstancesofthisattributemaybeapplied nization type. A relationship instance will only relate to a single type instance as long as no two non-> two instances of types that are related in the ontology. predicates evaluate to True on the same input. Only For example, (Level 3 Communications, AS3356) is an oneinstanceofthisattributewith>maybepresent; instanceofthe(ASOrganization,AS)relationshiptype if it is, then all other instances of the attribute for andindicatesthatAS3356isamemberofLevel3Com- the type instance are ignored. munications. The attributes of a type instance provide Thisattributeallowstheusertoexpressbeliefsabout information that users can incorporate into their trust the effect of compromise of one type instance on its beliefs, such as the location of a given Tor relay. The children, either uniformly or according to type. For world can be modified by users in ways provided by example, a compromised AS might attempt to com- thetrustlanguage.Weassumethateachinstancehasa promiseallofitsrouters;withsomeprobability(e.g., unique identifier and an indication of the type of which it is an instance. For our ontology, the system generates a world as follows: 2 The resources needed to compromise instances of different 1. ThecurrentTorconsensusandtheserverdescriptors typesmayvarywidely.However,weincludethesecondvariant itreferencesareusedtocreatethefollowinginstances sothatabudgetthatcoversallofaninstance’schildrencanbe modeledinsomefashion. and attributes, which concern relays: Unauthenticated Download Date | 4/21/15 5:21 PM 20,000InLeagueUndertheSea 10 – Tor Relay: An instance is created for each relay trolsmultipleASesorIXPs,suchasacompany.The in the consensus. clusters are used to create the following instances: – Relay Family: An instance is created for each – ASOrganization:Aninstanceiscreatedforeach connected component of relays, where two relays AS cluster. areconnectediftheymutuallyreferenceeachother – IXP Organization: An instance is created for in the family section of their descriptors [11]. each IXP cluster. – (Relay Family, Tor Relay):Aninstanceofthis – (AS Organization, AS):Aninstance ofthisre- relationship is created for each relay belonging to lationship is created for each AS in a given AS a given family. cluster. – RelaySoftwareType:Thisattributeisaddedto – (IXP Organization, IXP): An instance of this eachrelaybasedontheoperatingsystemreported relationshipiscreatedforeachIXPinagivenIXP in the relay’s descriptor. cluster. 2. Standardtechniques[22]areusedtoconstructanAS- 5. The system provides physical locations and legal ju- level Internet routing map. Data that can be used risdictions for several of the ontology types. IP loca- to create such a map includes the CAIDA internet tion information, such as from the MaxMind GeoIP topology [8], the CAIDA AS relationships [7], and database [26], provides location information for enti- RouteViews[31].Thismapisthenusedtocreatethe ties with IP addresses. The location of IXPs is fre- following instances: quently available on the Web as well [3]. The bilat- – Virtual Link: An instance is created represent- eral MLATs that might apply are obtained from the ing the path between each Autonomous System MLAT.is database [9]. These data are used to create and possible guard as well as between each Au- the following instances and attributes: tonomous System and exit. A possible guard is a – Legal jurisdiction: An instance of this type is Tor relay that satisfies the requirements to serve created for each country. as an entry guard. Guards and exits are deter- – (Legal jurisdiction, Relay):Aninstanceofthis mined from the Tor consensus. A virtual-link in- relationship is created for each relay in a given stancerepresentsbothdirectedpathsbetweenthe country, as determined by the relay’s IP address Autonomous System and relay, which may differ and the IP location information. due to Internet route asymmetries [15]. – (Legal jurisdiction, IXP): An instance of this – AS: An instance is created for each AS observed relationship is created for each IXP in a given in the RouteViews data. country, as determined by the IP addresses of the – (AS,VirtualLink):Aninstanceofthisrelation- IXP or other public IXP information. ship is created for each AS that appears on the – Physical location: This attribute is added to path in either direction between the virtual link’s each relay with its geographic coordinates (i.e., AS and its relay, as determined by the Internet latitudeandlongitude),asdeterminedfromitsIP routing map. address. This attribute is also added to each IXP 3. Internet Exchange Points (IXPs) are added to paths with its geographic coordinates, based on its IP in the AS-level Internet map based on data from the addresses or other public IXP information. IXP Mapping Project [3]. These additions are used – MLAT: As a preliminary step, for each country to create the following instances: instanceC,createaduplicatecountryinstanceC0, – IXP: An instance is created for each IXP that and add a relationship instance from C0 to C. For appears on at least one path in the Internet map. eachin-force,bilateralMLAT,createanMLATin- – (IXP, Virtual Link): An instance of this rela- stance(weassumethereisatmostoneperpairof tionship is created for each IXP that appears on countries). For each MLAT instance M, if C and 1 the path in either direction between the virtual C are the instances of the two countries involved 2 link’s AS and its relay, as determined by the In- in the corresponding MLAT, add relationship in- ternet routing map. stances from C0 and C0 to M and from M to C 1 2 1 4. ASes are clustered into organizations using the re- andC .TheduplicateC0 instanceswillbetheini- 2 sults of Cai et al. [5], and IXPs are clustered into tially compromised ones. The structure described organizations using the results of Johnson et al. [22]. here will propagate this compromise to the origi- Eachclusterrepresentsasinglelegalentitythatcon- nalC instances,eitherdirectlyorthroughMLATs. Here,wetakethedefaulteffectivenesstobe1,i.e., Unauthenticated Download Date | 4/21/15 5:21 PM 20,000InLeagueUndertheSea 11 each country always compromises its MLAT part- instance is then added to the system-generated world. ners, but this may be changed by the user on a The type of the instance may be system-generated, in per-MLAT basis. which case this belief represents an edit to the system- 6. Although the system does not provide information generated world, or it may be user-generated. If the in- aboutphysicalconnectionsingeneral,itcanuseaca- stance’s type is user-generated, then the user must de- bledatabasesuchastheTeleGeographydatabase[29] scribe to the system how the instance should be trans- or Greg’s Cable Map [25] to add a cable instance for lated to the BBN that the system produces from the each cable in the database. It would still be left to edited world. the user to identify which virtual links use which ca- For edges, a user may believe that one type in- bles,althoughincorporatingthisintothesystemisa stanceistheparentofanothertypeinstance.Herbelief topic of ongoing work. aboutsucharelationshipmustincludeanyrequiredat- tributesofthecorrespondingedgetypeintheontology. This relationship instance is then added to the system- 4 Beliefs and BBNs generated world. If the edge type is not part of the on- tology, the user must describe how the edge affects the computation of values in the BBN that the system pro- The user may provide various data to inform the oper- duces. ationofthesystem.However,manyusersmaynotwish Finally, the user provides trust beliefs of four types to do this, and the system includes a default belief set thatareusedinconstructingtheBBNfromtherevised designed to provide good security for average users. In world. The first two types of trust beliefs concern the Section 6 we describe a possible default belief set. For propagation of compromise. Budget beliefs allow the simplicity, we refer to beliefs as being provided by the user to say that an instance I in the edited world has user, but wherever they are not, the defaults are used the resources (monetary or otherwise) to compromise instead. k of its children that satisfy some predicate P. Enforc- ingthisasahardboundappearstobecomputationally harder than we are willing to use in the BBN, so we do 4.1 User beliefs this in expectation. Compromise-effectiveness (CE) be- liefsallowtheusertoexpresssomecorrelationsbetween Broadly, users may have two kinds of beliefs: those thecompromisesofnodesbysayingthat,if aninstance aboutthestructureofthenetwork,etc.,andthoseabout I is compromised, then, with probability p, all of I’s trust. The user’s structural beliefs are used to edit the children satisfying a predicate P are compromised. For system-generated world to produce an “edited world;” example, this captures the possibility that a compro- weexpectthiswillbedoneonce,notonaper-adversary mised AS compromises all of its routers except those of basis.Thesebeliefsmaydescribenewtypesandthead- aparticularmodel,forwhichtheAShasmadeanerror ditionorremovaloftypeinstancesandrelationshipsbe- in their (common) configuration file. tween them (e.g., adding relay operators known to the Theothertwotypesoftrustbeliefsconcernthelike- user). The user may also define new attributes, change lihood of compromise. Relative beliefs allow the user to the system-provided attributes, or provide values for say that instances satisfying a given predicate (e.g., re- emptyattributes(e.g.,labelingcountriesbytheirlarger lays running a buggy OS, network links that traverse a geographic region). submarine cable, or ASes that are small as determined The user’s beliefs may incorporate boolean pred- by their number of routers) have a certain probability icates that are evaluated on instances in the revised of compromise. (In particular, it specifies the probabil- world. For example, the user may have increased trust ity that they remain uncompromised if they are other- in ASes above a certain size. We sketch a suitable lan- wise uncompromised.) Absolute beliefs allow the user guage for this in App. A, but this can be replaced with to say that instances satisfying a given predicate (e.g., another if desired. thenodeisanASandtheASnumberis7007)arecom- A user may have structural beliefs about instances promised with a certain probability, regardless of other of types and edges from the ontology. For types, a user factors. maybelievethataninstanceofthattypeexists;herbe- liefaboutthatinstancemustincludeauniqueidentifier for the instance and any required attributes. This type Unauthenticated Download Date | 4/21/15 5:21 PM 20,000InLeagueUndertheSea 12 4.2 Sample belief language 4.2.2 Trust beliefs We now describe a sample language for users’ struc- Relative beliefs Thesearebeliefsoftheform(s,P,v), tural and trust beliefs. This incorporates predicates, wheresisastringotherthan00abs00,Pisapredicate which might be expressed using the predicate language on factor variables, and v ∈V. just outlined. In general, we assume that there is a Note that, in our translation procedure below, rel- set V of values that the user may use to express lev- ative beliefs affect the probability of compromise of els of trust. We illustrate this here by taking V to be a factor variable in the BBN that is not otherwise {SC,LC,U,LT,ST}; we think of these as “Surely Com- compromised through the causal relationships cap- promised,”“LikelyCompromised,”“Unknown,”“Likely tured in the world. Trustworthy,” and “Surely Trustworthy.” Our examples Absolute beliefs These are beliefs of the form will not rely on V having exactly five elements, but we (00abs00,P,v), where P is a predicate on factor vari- think this is one natural way that users might think ables and v ∈ V. A belief such as this says that the about their trust in network elements. chanceavariablesatisfyingPiscompromisediscap- tured by v. Note that it is the user’s responsibility to ensure that no two different absolute beliefs have 4.2.1 Structural beliefs predicatesthataresimultaneouslysatisfiedbyanode if those beliefs have different values for v. We do not LetRbethesetofrelationshipinstancesinthesystem- specify what value is used if this assumption is vio- created world. R0 will be R augmented with all of the lated.5 user-specified relationships. Budget Expressed as either (00bu100,I,T,k) or (00bu200, Novel types A user may define new types via expres- I,>,k), where 00bu100 and 00bu100 are string literals, I sions of the form (00ut00,tname,structreq,structopt), is a type instance in the edited world, T is a type where 00ut00 is a string literal, tname is a string (the in the edited world, and k is an integer. The inter- nameofthetype)thatmustbedistinctfromallother pretation is that, in expectation, compromise of the tnamevaluestheuserspecifiesandfromallelements type instance with a Budget attribute will lead to ofT,andwherestruct andstructoptarebothde- compromiseofk ofitschildren(oftypeT inthefirst req scriptions of data structures (these may be empty variant, or of all its children in the second variant). data structures, which might be indicated by NULL). Compromise effectiveness Expressed as either We write T0 for the set containing the elements of (00ce100,I, T together with all of the tname values provided by Pce,v) or (00ce200,I,>,v), where 00ce100 and 00ce200 the user. are string literals, I is an instance of a non-output Type instances An ordered list of tuples (T,D,n) type in the edited world, P is a predicate on in- ce T ∈ T0, D is a data structure that is valid for T, stances of a fixed type, > is a distinguished symbol, and n is a unique identifier among these tuples.3 and v ∈ V. The interpretation is that, if instance WewriteI0 forthesetformedbyaugmentingI with I is compromised, then it compromises its children these new instances. satisfying P (or all children, if > is given) with ce Relationship instances A set of pairs (P,C), where probability corresponding to v. P (parent)andC(child)aretypeinstancesfromI0.4 The actual probabilities that a compromised net- We do not need to specify new relationship types, workelementcompromisesotherelementsitcontrols, only the additional relationship instances. whichCEbeliefsattempttocapture,maytendtofall in a different range than other probabilities of com- promise. Our translation procedure could be modi- fied to treat the value v in a CE belief as a different probability than is used for other types of beliefs. Similarly, the belief language could be modified to 3 Weassumethatthesystemprovidesuniqueidentifiersforthe system-generatedtypeinstancesandthatthevaluesofninthe user’slistoftuplesaredistinctfromthoseidentifiers. 4 We abuse notation and use P and C in place of the unique 5 Anaturalapproachistoallowtheusetospecifytheseinan identifiersassociatedwitheachtypeinstanceintheeditedworld. orderedlistandusingthelastsatisfiedpredicate. Unauthenticated Download Date | 4/21/15 5:21 PM