updateFallbackDirs.py 78 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982
  1. #!/usr/bin/python
  2. # Usage: scripts/maint/updateFallbackDirs.py > src/or/fallback_dirs.inc
  3. #
  4. # This script should be run from a stable, reliable network connection,
  5. # with no other network activity (and not over tor).
  6. # If this is not possible, please disable:
  7. # PERFORM_IPV4_DIRPORT_CHECKS and PERFORM_IPV6_DIRPORT_CHECKS
  8. #
  9. # Needs dateutil (and potentially other python packages)
  10. # Needs stem available in your PYTHONPATH, or just ln -s ../stem/stem .
  11. # Optionally uses ipaddress (python 3 builtin) or py2-ipaddress (package)
  12. # for netblock analysis, in PYTHONPATH, or just
  13. # ln -s ../py2-ipaddress-3.4.1/ipaddress.py .
  14. #
  15. # Then read the logs to make sure the fallbacks aren't dominated by a single
  16. # netblock or port
  17. # Script by weasel, April 2015
  18. # Portions by gsathya & karsten, 2013
  19. # https://trac.torproject.org/projects/tor/attachment/ticket/8374/dir_list.2.py
  20. # Modifications by teor, 2015
  21. import StringIO
  22. import string
  23. import re
  24. import datetime
  25. import gzip
  26. import os.path
  27. import json
  28. import math
  29. import sys
  30. import urllib
  31. import urllib2
  32. import hashlib
  33. import dateutil.parser
  34. # bson_lazy provides bson
  35. #from bson import json_util
  36. import copy
  37. from stem.descriptor.remote import DescriptorDownloader
  38. import logging
  39. # INFO tells you why each relay was included or excluded
  40. # WARN tells you about potential misconfigurations and relay detail changes
  41. logging.basicConfig(level=logging.WARNING)
  42. logging.root.name = ''
  43. # INFO tells you about each consensus download attempt
  44. logging.getLogger('stem').setLevel(logging.WARNING)
  45. HAVE_IPADDRESS = False
  46. try:
  47. # python 3 builtin, or install package py2-ipaddress
  48. # there are several ipaddress implementations for python 2
  49. # with slightly different semantics with str typed text
  50. # fortunately, all our IP addresses are in unicode
  51. import ipaddress
  52. HAVE_IPADDRESS = True
  53. except ImportError:
  54. # if this happens, we avoid doing netblock analysis
  55. logging.warning('Unable to import ipaddress, please install py2-ipaddress.' +
  56. ' A fallback list will be created, but optional netblock' +
  57. ' analysis will not be performed.')
  58. ## Top-Level Configuration
  59. # Output all candidate fallbacks, or only output selected fallbacks?
  60. OUTPUT_CANDIDATES = False
  61. # Perform DirPort checks over IPv4?
  62. # Change this to False if IPv4 doesn't work for you, or if you don't want to
  63. # download a consensus for each fallback
  64. # Don't check ~1000 candidates when OUTPUT_CANDIDATES is True
  65. PERFORM_IPV4_DIRPORT_CHECKS = False if OUTPUT_CANDIDATES else True
  66. # Perform DirPort checks over IPv6?
  67. # If you know IPv6 works for you, set this to True
  68. # This will exclude IPv6 relays without an IPv6 DirPort configured
  69. # So it's best left at False until #18394 is implemented
  70. # Don't check ~1000 candidates when OUTPUT_CANDIDATES is True
  71. PERFORM_IPV6_DIRPORT_CHECKS = False if OUTPUT_CANDIDATES else False
  72. # Output fallback name, flags, and ContactInfo in a C comment?
  73. OUTPUT_COMMENTS = True if OUTPUT_CANDIDATES else False
  74. # Output matching ContactInfo in fallbacks list or the blacklist?
  75. # Useful if you're trying to contact operators
  76. CONTACT_COUNT = True if OUTPUT_CANDIDATES else False
  77. CONTACT_BLACKLIST_COUNT = True if OUTPUT_CANDIDATES else False
  78. ## OnionOO Settings
  79. ONIONOO = 'https://onionoo.torproject.org/'
  80. #ONIONOO = 'https://onionoo.thecthulhu.com/'
  81. # Don't bother going out to the Internet, just use the files available locally,
  82. # even if they're very old
  83. LOCAL_FILES_ONLY = False
  84. ## Whitelist / Blacklist Filter Settings
  85. # The whitelist contains entries that are included if all attributes match
  86. # (IPv4, dirport, orport, id, and optionally IPv6 and IPv6 orport)
  87. # The blacklist contains (partial) entries that are excluded if any
  88. # sufficiently specific group of attributes matches:
  89. # IPv4 & DirPort
  90. # IPv4 & ORPort
  91. # ID
  92. # IPv6 & DirPort
  93. # IPv6 & IPv6 ORPort
  94. # If neither port is included in the blacklist, the entire IP address is
  95. # blacklisted.
  96. # What happens to entries in neither list?
  97. # When True, they are included, when False, they are excluded
  98. INCLUDE_UNLISTED_ENTRIES = True if OUTPUT_CANDIDATES else False
  99. # If an entry is in both lists, what happens?
  100. # When True, it is excluded, when False, it is included
  101. BLACKLIST_EXCLUDES_WHITELIST_ENTRIES = True
  102. WHITELIST_FILE_NAME = 'scripts/maint/fallback.whitelist'
  103. BLACKLIST_FILE_NAME = 'scripts/maint/fallback.blacklist'
  104. # The number of bytes we'll read from a filter file before giving up
  105. MAX_LIST_FILE_SIZE = 1024 * 1024
  106. ## Eligibility Settings
  107. # Reduced due to a bug in tor where a relay submits a 0 DirPort when restarted
  108. # This causes OnionOO to (correctly) reset its stability timer
  109. # This issue will be fixed in 0.2.7.7 and 0.2.8.2
  110. # Until then, the CUTOFFs below ensure a decent level of stability.
  111. ADDRESS_AND_PORT_STABLE_DAYS = 7
  112. # What time-weighted-fraction of these flags must FallbackDirs
  113. # Equal or Exceed?
  114. CUTOFF_RUNNING = .95
  115. CUTOFF_V2DIR = .95
  116. CUTOFF_GUARD = .95
  117. # What time-weighted-fraction of these flags must FallbackDirs
  118. # Equal or Fall Under?
  119. # .00 means no bad exits
  120. PERMITTED_BADEXIT = .00
  121. # older entries' weights are adjusted with ALPHA^(age in days)
  122. AGE_ALPHA = 0.99
  123. # this factor is used to scale OnionOO entries to [0,1]
  124. ONIONOO_SCALE_ONE = 999.
  125. ## Fallback Count Limits
  126. # The target for these parameters is 20% of the guards in the network
  127. # This is around 200 as of October 2015
  128. _FB_POG = 0.2
  129. FALLBACK_PROPORTION_OF_GUARDS = None if OUTPUT_CANDIDATES else _FB_POG
  130. # We want exactly 100 fallbacks for the initial release
  131. # This gives us scope to add extra fallbacks to the list as needed
  132. # Limit the number of fallbacks (eliminating lowest by advertised bandwidth)
  133. MAX_FALLBACK_COUNT = None if OUTPUT_CANDIDATES else 100
  134. # Emit a C #error if the number of fallbacks is below
  135. MIN_FALLBACK_COUNT = 100
  136. ## Fallback Bandwidth Requirements
  137. # Any fallback with the Exit flag has its bandwidth multipled by this fraction
  138. # to make sure we aren't further overloading exits
  139. # (Set to 1.0, because we asked that only lightly loaded exits opt-in,
  140. # and the extra load really isn't that much for large relays.)
  141. EXIT_BANDWIDTH_FRACTION = 1.0
  142. # If a single fallback's bandwidth is too low, it's pointless adding it
  143. # We expect fallbacks to handle an extra 30 kilobytes per second of traffic
  144. # Make sure they can support a hundred times the expected extra load
  145. # (Use 102.4 to make it come out nicely in MB/s)
  146. # We convert this to a consensus weight before applying the filter,
  147. # because all the bandwidth amounts are specified by the relay
  148. MIN_BANDWIDTH = 102.4 * 30.0 * 1024.0
  149. # Clients will time out after 30 seconds trying to download a consensus
  150. # So allow fallback directories half that to deliver a consensus
  151. # The exact download times might change based on the network connection
  152. # running this script, but only by a few seconds
  153. # There is also about a second of python overhead
  154. CONSENSUS_DOWNLOAD_SPEED_MAX = 15.0
  155. # If the relay fails a consensus check, retry the download
  156. # This avoids delisting a relay due to transient network conditions
  157. CONSENSUS_DOWNLOAD_RETRY = True
  158. ## Fallback Weights for Client Selection
  159. # All fallback weights are equal, and set to the value below
  160. # Authorities are weighted 1.0 by default
  161. # Clients use these weights to select fallbacks and authorities at random
  162. # If there are 100 fallbacks and 9 authorities:
  163. # - each fallback is chosen with probability 10.0/(10.0*100 + 1.0*9) ~= 0.99%
  164. # - each authority is chosen with probability 1.0/(10.0*100 + 1.0*9) ~= 0.09%
  165. # A client choosing a bootstrap directory server will choose a fallback for
  166. # 10.0/(10.0*100 + 1.0*9) * 100 = 99.1% of attempts, and an authority for
  167. # 1.0/(10.0*100 + 1.0*9) * 9 = 0.9% of attempts.
  168. # (This disregards the bootstrap schedules, where clients start by choosing
  169. # from fallbacks & authoritites, then later choose from only authorities.)
  170. FALLBACK_OUTPUT_WEIGHT = 10.0
  171. ## Parsing Functions
  172. def parse_ts(t):
  173. return datetime.datetime.strptime(t, "%Y-%m-%d %H:%M:%S")
  174. def remove_bad_chars(raw_string, bad_char_list):
  175. # Remove each character in the bad_char_list
  176. cleansed_string = raw_string
  177. for c in bad_char_list:
  178. cleansed_string = cleansed_string.replace(c, '')
  179. return cleansed_string
  180. def cleanse_unprintable(raw_string):
  181. # Remove all unprintable characters
  182. cleansed_string = ''
  183. for c in raw_string:
  184. if c in string.printable:
  185. cleansed_string += c
  186. return cleansed_string
  187. def cleanse_whitespace(raw_string):
  188. # Replace all whitespace characters with a space
  189. cleansed_string = raw_string
  190. for c in string.whitespace:
  191. cleansed_string = cleansed_string.replace(c, ' ')
  192. return cleansed_string
  193. def cleanse_c_multiline_comment(raw_string):
  194. cleansed_string = raw_string
  195. # Embedded newlines should be removed by tor/onionoo, but let's be paranoid
  196. cleansed_string = cleanse_whitespace(cleansed_string)
  197. # ContactInfo and Version can be arbitrary binary data
  198. cleansed_string = cleanse_unprintable(cleansed_string)
  199. # Prevent a malicious / unanticipated string from breaking out
  200. # of a C-style multiline comment
  201. # This removes '/*' and '*/' and '//'
  202. bad_char_list = '*/'
  203. # Prevent a malicious string from using C nulls
  204. bad_char_list += '\0'
  205. # Be safer by removing bad characters entirely
  206. cleansed_string = remove_bad_chars(cleansed_string, bad_char_list)
  207. # Some compilers may further process the content of comments
  208. # There isn't much we can do to cover every possible case
  209. # But comment-based directives are typically only advisory
  210. return cleansed_string
  211. def cleanse_c_string(raw_string):
  212. cleansed_string = raw_string
  213. # Embedded newlines should be removed by tor/onionoo, but let's be paranoid
  214. cleansed_string = cleanse_whitespace(cleansed_string)
  215. # ContactInfo and Version can be arbitrary binary data
  216. cleansed_string = cleanse_unprintable(cleansed_string)
  217. # Prevent a malicious address/fingerprint string from breaking out
  218. # of a C-style string
  219. bad_char_list = '"'
  220. # Prevent a malicious string from using escapes
  221. bad_char_list += '\\'
  222. # Prevent a malicious string from using C nulls
  223. bad_char_list += '\0'
  224. # Be safer by removing bad characters entirely
  225. cleansed_string = remove_bad_chars(cleansed_string, bad_char_list)
  226. # Some compilers may further process the content of strings
  227. # There isn't much we can do to cover every possible case
  228. # But this typically only results in changes to the string data
  229. return cleansed_string
  230. ## OnionOO Source Functions
  231. # a dictionary of source metadata for each onionoo query we've made
  232. fetch_source = {}
  233. # register source metadata for 'what'
  234. # assumes we only retrieve one document for each 'what'
  235. def register_fetch_source(what, url, relays_published, version):
  236. fetch_source[what] = {}
  237. fetch_source[what]['url'] = url
  238. fetch_source[what]['relays_published'] = relays_published
  239. fetch_source[what]['version'] = version
  240. # list each registered source's 'what'
  241. def fetch_source_list():
  242. return sorted(fetch_source.keys())
  243. # given 'what', provide a multiline C comment describing the source
  244. def describe_fetch_source(what):
  245. desc = '/*'
  246. desc += '\n'
  247. desc += 'Onionoo Source: '
  248. desc += cleanse_c_multiline_comment(what)
  249. desc += ' Date: '
  250. desc += cleanse_c_multiline_comment(fetch_source[what]['relays_published'])
  251. desc += ' Version: '
  252. desc += cleanse_c_multiline_comment(fetch_source[what]['version'])
  253. desc += '\n'
  254. desc += 'URL: '
  255. desc += cleanse_c_multiline_comment(fetch_source[what]['url'])
  256. desc += '\n'
  257. desc += '*/'
  258. return desc
  259. ## File Processing Functions
  260. def write_to_file(str, file_name, max_len):
  261. try:
  262. with open(file_name, 'w') as f:
  263. f.write(str[0:max_len])
  264. except EnvironmentError, error:
  265. logging.error('Writing file %s failed: %d: %s'%
  266. (file_name,
  267. error.errno,
  268. error.strerror)
  269. )
  270. def read_from_file(file_name, max_len):
  271. try:
  272. if os.path.isfile(file_name):
  273. with open(file_name, 'r') as f:
  274. return f.read(max_len)
  275. except EnvironmentError, error:
  276. logging.info('Loading file %s failed: %d: %s'%
  277. (file_name,
  278. error.errno,
  279. error.strerror)
  280. )
  281. return None
  282. def load_possibly_compressed_response_json(response):
  283. if response.info().get('Content-Encoding') == 'gzip':
  284. buf = StringIO.StringIO( response.read() )
  285. f = gzip.GzipFile(fileobj=buf)
  286. return json.load(f)
  287. else:
  288. return json.load(response)
  289. def load_json_from_file(json_file_name):
  290. # An exception here may be resolved by deleting the .last_modified
  291. # and .json files, and re-running the script
  292. try:
  293. with open(json_file_name, 'r') as f:
  294. return json.load(f)
  295. except EnvironmentError, error:
  296. raise Exception('Reading not-modified json file %s failed: %d: %s'%
  297. (json_file_name,
  298. error.errno,
  299. error.strerror)
  300. )
  301. ## OnionOO Functions
  302. def datestr_to_datetime(datestr):
  303. # Parse datetimes like: Fri, 02 Oct 2015 13:34:14 GMT
  304. if datestr is not None:
  305. dt = dateutil.parser.parse(datestr)
  306. else:
  307. # Never modified - use start of epoch
  308. dt = datetime.datetime.utcfromtimestamp(0)
  309. # strip any timezone out (in case they're supported in future)
  310. dt = dt.replace(tzinfo=None)
  311. return dt
  312. def onionoo_fetch(what, **kwargs):
  313. params = kwargs
  314. params['type'] = 'relay'
  315. #params['limit'] = 10
  316. params['first_seen_days'] = '%d-'%(ADDRESS_AND_PORT_STABLE_DAYS,)
  317. params['last_seen_days'] = '-7'
  318. params['flag'] = 'V2Dir'
  319. url = ONIONOO + what + '?' + urllib.urlencode(params)
  320. # Unfortunately, the URL is too long for some OS filenames,
  321. # but we still don't want to get files from different URLs mixed up
  322. base_file_name = what + '-' + hashlib.sha1(url).hexdigest()
  323. full_url_file_name = base_file_name + '.full_url'
  324. MAX_FULL_URL_LENGTH = 1024
  325. last_modified_file_name = base_file_name + '.last_modified'
  326. MAX_LAST_MODIFIED_LENGTH = 64
  327. json_file_name = base_file_name + '.json'
  328. if LOCAL_FILES_ONLY:
  329. # Read from the local file, don't write to anything
  330. response_json = load_json_from_file(json_file_name)
  331. else:
  332. # store the full URL to a file for debugging
  333. # no need to compare as long as you trust SHA-1
  334. write_to_file(url, full_url_file_name, MAX_FULL_URL_LENGTH)
  335. request = urllib2.Request(url)
  336. request.add_header('Accept-encoding', 'gzip')
  337. # load the last modified date from the file, if it exists
  338. last_mod_date = read_from_file(last_modified_file_name,
  339. MAX_LAST_MODIFIED_LENGTH)
  340. if last_mod_date is not None:
  341. request.add_header('If-modified-since', last_mod_date)
  342. # Parse last modified date
  343. last_mod = datestr_to_datetime(last_mod_date)
  344. # Not Modified and still recent enough to be useful
  345. # Onionoo / Globe used to use 6 hours, but we can afford a day
  346. required_freshness = datetime.datetime.utcnow()
  347. # strip any timezone out (to match dateutil.parser)
  348. required_freshness = required_freshness.replace(tzinfo=None)
  349. required_freshness -= datetime.timedelta(hours=24)
  350. # Make the OnionOO request
  351. response_code = 0
  352. try:
  353. response = urllib2.urlopen(request)
  354. response_code = response.getcode()
  355. except urllib2.HTTPError, error:
  356. response_code = error.code
  357. if response_code == 304: # not modified
  358. pass
  359. else:
  360. raise Exception("Could not get " + url + ": "
  361. + str(error.code) + ": " + error.reason)
  362. if response_code == 200: # OK
  363. last_mod = datestr_to_datetime(response.info().get('Last-Modified'))
  364. # Check for freshness
  365. if last_mod < required_freshness:
  366. if last_mod_date is not None:
  367. # This check sometimes fails transiently, retry the script if it does
  368. date_message = "Outdated data: last updated " + last_mod_date
  369. else:
  370. date_message = "No data: never downloaded "
  371. raise Exception(date_message + " from " + url)
  372. # Process the data
  373. if response_code == 200: # OK
  374. response_json = load_possibly_compressed_response_json(response)
  375. with open(json_file_name, 'w') as f:
  376. # use the most compact json representation to save space
  377. json.dump(response_json, f, separators=(',',':'))
  378. # store the last modified date in its own file
  379. if response.info().get('Last-modified') is not None:
  380. write_to_file(response.info().get('Last-Modified'),
  381. last_modified_file_name,
  382. MAX_LAST_MODIFIED_LENGTH)
  383. elif response_code == 304: # Not Modified
  384. response_json = load_json_from_file(json_file_name)
  385. else: # Unexpected HTTP response code not covered in the HTTPError above
  386. raise Exception("Unexpected HTTP response code to " + url + ": "
  387. + str(response_code))
  388. register_fetch_source(what,
  389. url,
  390. response_json['relays_published'],
  391. response_json['version'])
  392. return response_json
  393. def fetch(what, **kwargs):
  394. #x = onionoo_fetch(what, **kwargs)
  395. # don't use sort_keys, as the order of or_addresses is significant
  396. #print json.dumps(x, indent=4, separators=(',', ': '))
  397. #sys.exit(0)
  398. return onionoo_fetch(what, **kwargs)
  399. ## Fallback Candidate Class
  400. class Candidate(object):
  401. CUTOFF_ADDRESS_AND_PORT_STABLE = (datetime.datetime.utcnow()
  402. - datetime.timedelta(ADDRESS_AND_PORT_STABLE_DAYS))
  403. def __init__(self, details):
  404. for f in ['fingerprint', 'nickname', 'last_changed_address_or_port',
  405. 'consensus_weight', 'or_addresses', 'dir_address']:
  406. if not f in details: raise Exception("Document has no %s field."%(f,))
  407. if not 'contact' in details:
  408. details['contact'] = None
  409. if not 'flags' in details or details['flags'] is None:
  410. details['flags'] = []
  411. if (not 'advertised_bandwidth' in details
  412. or details['advertised_bandwidth'] is None):
  413. # relays without advertised bandwdith have it calculated from their
  414. # consensus weight
  415. details['advertised_bandwidth'] = 0
  416. if (not 'effective_family' in details
  417. or details['effective_family'] is None):
  418. details['effective_family'] = []
  419. details['last_changed_address_or_port'] = parse_ts(
  420. details['last_changed_address_or_port'])
  421. self._data = details
  422. self._stable_sort_or_addresses()
  423. self._fpr = self._data['fingerprint']
  424. self._running = self._guard = self._v2dir = 0.
  425. self._split_dirport()
  426. self._compute_orport()
  427. if self.orport is None:
  428. raise Exception("Failed to get an orport for %s."%(self._fpr,))
  429. self._compute_ipv6addr()
  430. if not self.has_ipv6():
  431. logging.debug("Failed to get an ipv6 address for %s."%(self._fpr,))
  432. def _stable_sort_or_addresses(self):
  433. # replace self._data['or_addresses'] with a stable ordering,
  434. # sorting the secondary addresses in string order
  435. # leave the received order in self._data['or_addresses_raw']
  436. self._data['or_addresses_raw'] = self._data['or_addresses']
  437. or_address_primary = self._data['or_addresses'][:1]
  438. # subsequent entries in the or_addresses array are in an arbitrary order
  439. # so we stabilise the addresses by sorting them in string order
  440. or_addresses_secondaries_stable = sorted(self._data['or_addresses'][1:])
  441. or_addresses_stable = or_address_primary + or_addresses_secondaries_stable
  442. self._data['or_addresses'] = or_addresses_stable
  443. def get_fingerprint(self):
  444. return self._fpr
  445. # is_valid_ipv[46]_address by gsathya, karsten, 2013
  446. @staticmethod
  447. def is_valid_ipv4_address(address):
  448. if not isinstance(address, (str, unicode)):
  449. return False
  450. # check if there are four period separated values
  451. if address.count(".") != 3:
  452. return False
  453. # checks that each value in the octet are decimal values between 0-255
  454. for entry in address.split("."):
  455. if not entry.isdigit() or int(entry) < 0 or int(entry) > 255:
  456. return False
  457. elif entry[0] == "0" and len(entry) > 1:
  458. return False # leading zeros, for instance in "1.2.3.001"
  459. return True
  460. @staticmethod
  461. def is_valid_ipv6_address(address):
  462. if not isinstance(address, (str, unicode)):
  463. return False
  464. # remove brackets
  465. address = address[1:-1]
  466. # addresses are made up of eight colon separated groups of four hex digits
  467. # with leading zeros being optional
  468. # https://en.wikipedia.org/wiki/IPv6#Address_format
  469. colon_count = address.count(":")
  470. if colon_count > 7:
  471. return False # too many groups
  472. elif colon_count != 7 and not "::" in address:
  473. return False # not enough groups and none are collapsed
  474. elif address.count("::") > 1 or ":::" in address:
  475. return False # multiple groupings of zeros can't be collapsed
  476. found_ipv4_on_previous_entry = False
  477. for entry in address.split(":"):
  478. # If an IPv6 address has an embedded IPv4 address,
  479. # it must be the last entry
  480. if found_ipv4_on_previous_entry:
  481. return False
  482. if not re.match("^[0-9a-fA-f]{0,4}$", entry):
  483. if not Candidate.is_valid_ipv4_address(entry):
  484. return False
  485. else:
  486. found_ipv4_on_previous_entry = True
  487. return True
  488. def _split_dirport(self):
  489. # Split the dir_address into dirip and dirport
  490. (self.dirip, _dirport) = self._data['dir_address'].split(':', 2)
  491. self.dirport = int(_dirport)
  492. def _compute_orport(self):
  493. # Choose the first ORPort that's on the same IPv4 address as the DirPort.
  494. # In rare circumstances, this might not be the primary ORPort address.
  495. # However, _stable_sort_or_addresses() ensures we choose the same one
  496. # every time, even if onionoo changes the order of the secondaries.
  497. self._split_dirport()
  498. self.orport = None
  499. for i in self._data['or_addresses']:
  500. if i != self._data['or_addresses'][0]:
  501. logging.debug('Secondary IPv4 Address Used for %s: %s'%(self._fpr, i))
  502. (ipaddr, port) = i.rsplit(':', 1)
  503. if (ipaddr == self.dirip) and Candidate.is_valid_ipv4_address(ipaddr):
  504. self.orport = int(port)
  505. return
  506. def _compute_ipv6addr(self):
  507. # Choose the first IPv6 address that uses the same port as the ORPort
  508. # Or, choose the first IPv6 address in the list
  509. # _stable_sort_or_addresses() ensures we choose the same IPv6 address
  510. # every time, even if onionoo changes the order of the secondaries.
  511. self.ipv6addr = None
  512. self.ipv6orport = None
  513. # Choose the first IPv6 address that uses the same port as the ORPort
  514. for i in self._data['or_addresses']:
  515. (ipaddr, port) = i.rsplit(':', 1)
  516. if (port == self.orport) and Candidate.is_valid_ipv6_address(ipaddr):
  517. self.ipv6addr = ipaddr
  518. self.ipv6orport = int(port)
  519. return
  520. # Choose the first IPv6 address in the list
  521. for i in self._data['or_addresses']:
  522. (ipaddr, port) = i.rsplit(':', 1)
  523. if Candidate.is_valid_ipv6_address(ipaddr):
  524. self.ipv6addr = ipaddr
  525. self.ipv6orport = int(port)
  526. return
  527. @staticmethod
  528. def _extract_generic_history(history, which='unknown'):
  529. # given a tree like this:
  530. # {
  531. # "1_month": {
  532. # "count": 187,
  533. # "factor": 0.001001001001001001,
  534. # "first": "2015-02-27 06:00:00",
  535. # "interval": 14400,
  536. # "last": "2015-03-30 06:00:00",
  537. # "values": [
  538. # 999,
  539. # 999
  540. # ]
  541. # },
  542. # "1_week": {
  543. # "count": 169,
  544. # "factor": 0.001001001001001001,
  545. # "first": "2015-03-23 07:30:00",
  546. # "interval": 3600,
  547. # "last": "2015-03-30 07:30:00",
  548. # "values": [ ...]
  549. # },
  550. # "1_year": {
  551. # "count": 177,
  552. # "factor": 0.001001001001001001,
  553. # "first": "2014-04-11 00:00:00",
  554. # "interval": 172800,
  555. # "last": "2015-03-29 00:00:00",
  556. # "values": [ ...]
  557. # },
  558. # "3_months": {
  559. # "count": 185,
  560. # "factor": 0.001001001001001001,
  561. # "first": "2014-12-28 06:00:00",
  562. # "interval": 43200,
  563. # "last": "2015-03-30 06:00:00",
  564. # "values": [ ...]
  565. # }
  566. # },
  567. # extract exactly one piece of data per time interval,
  568. # using smaller intervals where available.
  569. #
  570. # returns list of (age, length, value) dictionaries.
  571. generic_history = []
  572. periods = history.keys()
  573. periods.sort(key = lambda x: history[x]['interval'])
  574. now = datetime.datetime.utcnow()
  575. newest = now
  576. for p in periods:
  577. h = history[p]
  578. interval = datetime.timedelta(seconds = h['interval'])
  579. this_ts = parse_ts(h['last'])
  580. if (len(h['values']) != h['count']):
  581. logging.warning('Inconsistent value count in %s document for %s'
  582. %(p, which))
  583. for v in reversed(h['values']):
  584. if (this_ts <= newest):
  585. agt1 = now - this_ts
  586. agt2 = interval
  587. agetmp1 = (agt1.microseconds + (agt1.seconds + agt1.days * 24 * 3600)
  588. * 10**6) / 10**6
  589. agetmp2 = (agt2.microseconds + (agt2.seconds + agt2.days * 24 * 3600)
  590. * 10**6) / 10**6
  591. generic_history.append(
  592. { 'age': agetmp1,
  593. 'length': agetmp2,
  594. 'value': v
  595. })
  596. newest = this_ts
  597. this_ts -= interval
  598. if (this_ts + interval != parse_ts(h['first'])):
  599. logging.warning('Inconsistent time information in %s document for %s'
  600. %(p, which))
  601. #print json.dumps(generic_history, sort_keys=True,
  602. # indent=4, separators=(',', ': '))
  603. return generic_history
  604. @staticmethod
  605. def _avg_generic_history(generic_history):
  606. a = []
  607. for i in generic_history:
  608. if i['age'] > (ADDRESS_AND_PORT_STABLE_DAYS * 24 * 3600):
  609. continue
  610. if (i['length'] is not None
  611. and i['age'] is not None
  612. and i['value'] is not None):
  613. w = i['length'] * math.pow(AGE_ALPHA, i['age']/(3600*24))
  614. a.append( (i['value'] * w, w) )
  615. sv = math.fsum(map(lambda x: x[0], a))
  616. sw = math.fsum(map(lambda x: x[1], a))
  617. if sw == 0.0:
  618. svw = 0.0
  619. else:
  620. svw = sv/sw
  621. return svw
  622. def _add_generic_history(self, history):
  623. periods = r['read_history'].keys()
  624. periods.sort(key = lambda x: r['read_history'][x]['interval'] )
  625. print periods
  626. def add_running_history(self, history):
  627. pass
  628. def add_uptime(self, uptime):
  629. logging.debug('Adding uptime %s.'%(self._fpr,))
  630. # flags we care about: Running, V2Dir, Guard
  631. if not 'flags' in uptime:
  632. logging.debug('No flags in document for %s.'%(self._fpr,))
  633. return
  634. for f in ['Running', 'Guard', 'V2Dir']:
  635. if not f in uptime['flags']:
  636. logging.debug('No %s in flags for %s.'%(f, self._fpr,))
  637. return
  638. running = self._extract_generic_history(uptime['flags']['Running'],
  639. '%s-Running'%(self._fpr))
  640. guard = self._extract_generic_history(uptime['flags']['Guard'],
  641. '%s-Guard'%(self._fpr))
  642. v2dir = self._extract_generic_history(uptime['flags']['V2Dir'],
  643. '%s-V2Dir'%(self._fpr))
  644. if 'BadExit' in uptime['flags']:
  645. badexit = self._extract_generic_history(uptime['flags']['BadExit'],
  646. '%s-BadExit'%(self._fpr))
  647. self._running = self._avg_generic_history(running) / ONIONOO_SCALE_ONE
  648. self._guard = self._avg_generic_history(guard) / ONIONOO_SCALE_ONE
  649. self._v2dir = self._avg_generic_history(v2dir) / ONIONOO_SCALE_ONE
  650. self._badexit = None
  651. if 'BadExit' in uptime['flags']:
  652. self._badexit = self._avg_generic_history(badexit) / ONIONOO_SCALE_ONE
  653. def is_candidate(self):
  654. must_be_running_now = (PERFORM_IPV4_DIRPORT_CHECKS
  655. or PERFORM_IPV6_DIRPORT_CHECKS)
  656. if (must_be_running_now and not self.is_running()):
  657. logging.info('%s not a candidate: not running now, unable to check ' +
  658. 'DirPort consensus download', self._fpr)
  659. return False
  660. if (self._data['last_changed_address_or_port'] >
  661. self.CUTOFF_ADDRESS_AND_PORT_STABLE):
  662. logging.info('%s not a candidate: changed address/port recently (%s)',
  663. self._fpr, self._data['last_changed_address_or_port'])
  664. return False
  665. if self._running < CUTOFF_RUNNING:
  666. logging.info('%s not a candidate: running avg too low (%lf)',
  667. self._fpr, self._running)
  668. return False
  669. if self._v2dir < CUTOFF_V2DIR:
  670. logging.info('%s not a candidate: v2dir avg too low (%lf)',
  671. self._fpr, self._v2dir)
  672. return False
  673. if self._badexit is not None and self._badexit > PERMITTED_BADEXIT:
  674. logging.info('%s not a candidate: badexit avg too high (%lf)',
  675. self._fpr, self._badexit)
  676. return False
  677. # if the relay doesn't report a version, also exclude the relay
  678. if (not self._data.has_key('recommended_version')
  679. or not self._data['recommended_version']):
  680. logging.info('%s not a candidate: version not recommended', self._fpr)
  681. return False
  682. if self._guard < CUTOFF_GUARD:
  683. logging.info('%s not a candidate: guard avg too low (%lf)',
  684. self._fpr, self._guard)
  685. return False
  686. if (not self._data.has_key('consensus_weight')
  687. or self._data['consensus_weight'] < 1):
  688. logging.info('%s not a candidate: consensus weight invalid', self._fpr)
  689. return False
  690. return True
  691. def is_in_whitelist(self, relaylist):
  692. """ A fallback matches if each key in the whitelist line matches:
  693. ipv4
  694. dirport
  695. orport
  696. id
  697. ipv6 address and port (if present)
  698. If the fallback has an ipv6 key, the whitelist line must also have
  699. it, and vice versa, otherwise they don't match. """
  700. ipv6 = None
  701. if self.has_ipv6():
  702. ipv6 = '%s:%d'%(self.ipv6addr, self.ipv6orport)
  703. for entry in relaylist:
  704. if entry['id'] != self._fpr:
  705. # can't log here unless we match an IP and port, because every relay's
  706. # fingerprint is compared to every entry's fingerprint
  707. if entry['ipv4'] == self.dirip and int(entry['orport']) == self.orport:
  708. logging.warning('%s excluded: has OR %s:%d changed fingerprint to ' +
  709. '%s?', entry['id'], self.dirip, self.orport,
  710. self._fpr)
  711. if self.has_ipv6() and entry.has_key('ipv6') and entry['ipv6'] == ipv6:
  712. logging.warning('%s excluded: has OR %s changed fingerprint to ' +
  713. '%s?', entry['id'], ipv6, self._fpr)
  714. continue
  715. if entry['ipv4'] != self.dirip:
  716. logging.warning('%s excluded: has it changed IPv4 from %s to %s?',
  717. self._fpr, entry['ipv4'], self.dirip)
  718. continue
  719. if int(entry['dirport']) != self.dirport:
  720. logging.warning('%s excluded: has it changed DirPort from %s:%d to ' +
  721. '%s:%d?', self._fpr, self.dirip, int(entry['dirport']),
  722. self.dirip, self.dirport)
  723. continue
  724. if int(entry['orport']) != self.orport:
  725. logging.warning('%s excluded: has it changed ORPort from %s:%d to ' +
  726. '%s:%d?', self._fpr, self.dirip, int(entry['orport']),
  727. self.dirip, self.orport)
  728. continue
  729. if entry.has_key('ipv6') and self.has_ipv6():
  730. # if both entry and fallback have an ipv6 address, compare them
  731. if entry['ipv6'] != ipv6:
  732. logging.warning('%s excluded: has it changed IPv6 ORPort from %s ' +
  733. 'to %s?', self._fpr, entry['ipv6'], ipv6)
  734. continue
  735. # if the fallback has an IPv6 address but the whitelist entry
  736. # doesn't, or vice versa, the whitelist entry doesn't match
  737. elif entry.has_key('ipv6') and not self.has_ipv6():
  738. logging.warning('%s excluded: has it lost its former IPv6 address %s?',
  739. self._fpr, entry['ipv6'])
  740. continue
  741. elif not entry.has_key('ipv6') and self.has_ipv6():
  742. logging.warning('%s excluded: has it gained an IPv6 address %s?',
  743. self._fpr, ipv6)
  744. continue
  745. return True
  746. return False
  747. def is_in_blacklist(self, relaylist):
  748. """ A fallback matches a blacklist line if a sufficiently specific group
  749. of attributes matches:
  750. ipv4 & dirport
  751. ipv4 & orport
  752. id
  753. ipv6 & dirport
  754. ipv6 & ipv6 orport
  755. If the fallback and the blacklist line both have an ipv6 key,
  756. their values will be compared, otherwise, they will be ignored.
  757. If there is no dirport and no orport, the entry matches all relays on
  758. that ip. """
  759. for entry in relaylist:
  760. for key in entry:
  761. value = entry[key]
  762. if key == 'id' and value == self._fpr:
  763. logging.info('%s is in the blacklist: fingerprint matches',
  764. self._fpr)
  765. return True
  766. if key == 'ipv4' and value == self.dirip:
  767. # if the dirport is present, check it too
  768. if entry.has_key('dirport'):
  769. if int(entry['dirport']) == self.dirport:
  770. logging.info('%s is in the blacklist: IPv4 (%s) and ' +
  771. 'DirPort (%d) match', self._fpr, self.dirip,
  772. self.dirport)
  773. return True
  774. # if the orport is present, check it too
  775. elif entry.has_key('orport'):
  776. if int(entry['orport']) == self.orport:
  777. logging.info('%s is in the blacklist: IPv4 (%s) and ' +
  778. 'ORPort (%d) match', self._fpr, self.dirip,
  779. self.orport)
  780. return True
  781. else:
  782. logging.info('%s is in the blacklist: IPv4 (%s) matches, and ' +
  783. 'entry has no DirPort or ORPort', self._fpr,
  784. self.dirip)
  785. return True
  786. ipv6 = None
  787. if self.has_ipv6():
  788. ipv6 = '%s:%d'%(self.ipv6addr, self.ipv6orport)
  789. if (key == 'ipv6' and self.has_ipv6()):
  790. # if both entry and fallback have an ipv6 address, compare them,
  791. # otherwise, disregard ipv6 addresses
  792. if value == ipv6:
  793. # if the dirport is present, check it too
  794. if entry.has_key('dirport'):
  795. if int(entry['dirport']) == self.dirport:
  796. logging.info('%s is in the blacklist: IPv6 (%s) and ' +
  797. 'DirPort (%d) match', self._fpr, ipv6,
  798. self.dirport)
  799. return True
  800. # we've already checked the ORPort, it's part of entry['ipv6']
  801. else:
  802. logging.info('%s is in the blacklist: IPv6 (%s) matches, and' +
  803. 'entry has no DirPort', self._fpr, ipv6)
  804. return True
  805. elif (key == 'ipv6' or self.has_ipv6()):
  806. # only log if the fingerprint matches but the IPv6 doesn't
  807. if entry.has_key('id') and entry['id'] == self._fpr:
  808. logging.info('%s skipping IPv6 blacklist comparison: relay ' +
  809. 'has%s IPv6%s, but entry has%s IPv6%s', self._fpr,
  810. '' if self.has_ipv6() else ' no',
  811. (' (' + ipv6 + ')') if self.has_ipv6() else '',
  812. '' if key == 'ipv6' else ' no',
  813. (' (' + value + ')') if key == 'ipv6' else '')
  814. logging.warning('Has %s %s IPv6 address %s?', self._fpr,
  815. 'gained an' if self.has_ipv6() else 'lost its former',
  816. ipv6 if self.has_ipv6() else value)
  817. return False
  818. def cw_to_bw_factor(self):
  819. # any relays with a missing or zero consensus weight are not candidates
  820. # any relays with a missing advertised bandwidth have it set to zero
  821. return self._data['advertised_bandwidth'] / self._data['consensus_weight']
  822. # since advertised_bandwidth is reported by the relay, it can be gamed
  823. # to avoid this, use the median consensus weight to bandwidth factor to
  824. # estimate this relay's measured bandwidth, and make that the upper limit
  825. def measured_bandwidth(self, median_cw_to_bw_factor):
  826. cw_to_bw= median_cw_to_bw_factor
  827. # Reduce exit bandwidth to make sure we're not overloading them
  828. if self.is_exit():
  829. cw_to_bw *= EXIT_BANDWIDTH_FRACTION
  830. measured_bandwidth = self._data['consensus_weight'] * cw_to_bw
  831. if self._data['advertised_bandwidth'] != 0:
  832. # limit advertised bandwidth (if available) to measured bandwidth
  833. return min(measured_bandwidth, self._data['advertised_bandwidth'])
  834. else:
  835. return measured_bandwidth
  836. def set_measured_bandwidth(self, median_cw_to_bw_factor):
  837. self._data['measured_bandwidth'] = self.measured_bandwidth(
  838. median_cw_to_bw_factor)
  839. def is_exit(self):
  840. return 'Exit' in self._data['flags']
  841. def is_guard(self):
  842. return 'Guard' in self._data['flags']
  843. def is_running(self):
  844. return 'Running' in self._data['flags']
  845. # does this fallback have an IPv6 address and orport?
  846. def has_ipv6(self):
  847. return self.ipv6addr is not None and self.ipv6orport is not None
  848. # strip leading and trailing brackets from an IPv6 address
  849. # safe to use on non-bracketed IPv6 and on IPv4 addresses
  850. # also convert to unicode, and make None appear as ''
  851. @staticmethod
  852. def strip_ipv6_brackets(ip):
  853. if ip is None:
  854. return unicode('')
  855. if len(ip) < 2:
  856. return unicode(ip)
  857. if ip[0] == '[' and ip[-1] == ']':
  858. return unicode(ip[1:-1])
  859. return unicode(ip)
  860. # are ip_a and ip_b in the same netblock?
  861. # mask_bits is the size of the netblock
  862. # takes both IPv4 and IPv6 addresses
  863. # the versions of ip_a and ip_b must be the same
  864. # the mask must be valid for the IP version
  865. @staticmethod
  866. def netblocks_equal(ip_a, ip_b, mask_bits):
  867. if ip_a is None or ip_b is None:
  868. return False
  869. ip_a = Candidate.strip_ipv6_brackets(ip_a)
  870. ip_b = Candidate.strip_ipv6_brackets(ip_b)
  871. a = ipaddress.ip_address(ip_a)
  872. b = ipaddress.ip_address(ip_b)
  873. if a.version != b.version:
  874. raise Exception('Mismatching IP versions in %s and %s'%(ip_a, ip_b))
  875. if mask_bits > a.max_prefixlen:
  876. logging.error('Bad IP mask %d for %s and %s'%(mask_bits, ip_a, ip_b))
  877. mask_bits = a.max_prefixlen
  878. if mask_bits < 0:
  879. logging.error('Bad IP mask %d for %s and %s'%(mask_bits, ip_a, ip_b))
  880. mask_bits = 0
  881. a_net = ipaddress.ip_network('%s/%d'%(ip_a, mask_bits), strict=False)
  882. return b in a_net
  883. # is this fallback's IPv4 address (dirip) in the same netblock as other's
  884. # IPv4 address?
  885. # mask_bits is the size of the netblock
  886. def ipv4_netblocks_equal(self, other, mask_bits):
  887. return Candidate.netblocks_equal(self.dirip, other.dirip, mask_bits)
  888. # is this fallback's IPv6 address (ipv6addr) in the same netblock as
  889. # other's IPv6 address?
  890. # Returns False if either fallback has no IPv6 address
  891. # mask_bits is the size of the netblock
  892. def ipv6_netblocks_equal(self, other, mask_bits):
  893. if not self.has_ipv6() or not other.has_ipv6():
  894. return False
  895. return Candidate.netblocks_equal(self.ipv6addr, other.ipv6addr, mask_bits)
  896. # is this fallback's IPv4 DirPort the same as other's IPv4 DirPort?
  897. def dirport_equal(self, other):
  898. return self.dirport == other.dirport
  899. # is this fallback's IPv4 ORPort the same as other's IPv4 ORPort?
  900. def ipv4_orport_equal(self, other):
  901. return self.orport == other.orport
  902. # is this fallback's IPv6 ORPort the same as other's IPv6 ORPort?
  903. # Returns False if either fallback has no IPv6 address
  904. def ipv6_orport_equal(self, other):
  905. if not self.has_ipv6() or not other.has_ipv6():
  906. return False
  907. return self.ipv6orport == other.ipv6orport
  908. # does this fallback have the same DirPort, IPv4 ORPort, or
  909. # IPv6 ORPort as other?
  910. # Ignores IPv6 ORPort if either fallback has no IPv6 address
  911. def port_equal(self, other):
  912. return (self.dirport_equal(other) or self.ipv4_orport_equal(other)
  913. or self.ipv6_orport_equal(other))
  914. # return a list containing IPv4 ORPort, DirPort, and IPv6 ORPort (if present)
  915. def port_list(self):
  916. ports = [self.dirport, self.orport]
  917. if self.has_ipv6() and not self.ipv6orport in ports:
  918. ports.append(self.ipv6orport)
  919. return ports
  920. # does this fallback share a port with other, regardless of whether the
  921. # port types match?
  922. # For example, if self's IPv4 ORPort is 80 and other's DirPort is 80,
  923. # return True
  924. def port_shared(self, other):
  925. for p in self.port_list():
  926. if p in other.port_list():
  927. return True
  928. return False
  929. # report how long it takes to download a consensus from dirip:dirport
  930. @staticmethod
  931. def fallback_consensus_download_speed(dirip, dirport, nickname, max_time):
  932. download_failed = False
  933. downloader = DescriptorDownloader()
  934. start = datetime.datetime.utcnow()
  935. # some directory mirrors respond to requests in ways that hang python
  936. # sockets, which is why we log this line here
  937. logging.info('Initiating consensus download from %s (%s:%d).', nickname,
  938. dirip, dirport)
  939. # there appears to be about 1 second of overhead when comparing stem's
  940. # internal trace time and the elapsed time calculated here
  941. TIMEOUT_SLOP = 1.0
  942. try:
  943. downloader.get_consensus(endpoints = [(dirip, dirport)],
  944. timeout = (max_time + TIMEOUT_SLOP),
  945. validate = True,
  946. retries = 0,
  947. fall_back_to_authority = False).run()
  948. except Exception, stem_error:
  949. logging.info('Unable to retrieve a consensus from %s: %s', nickname,
  950. stem_error)
  951. status = 'error: "%s"' % (stem_error)
  952. level = logging.WARNING
  953. download_failed = True
  954. elapsed = (datetime.datetime.utcnow() - start).total_seconds()
  955. if elapsed > max_time:
  956. status = 'too slow'
  957. level = logging.WARNING
  958. download_failed = True
  959. else:
  960. status = 'ok'
  961. level = logging.DEBUG
  962. logging.log(level, 'Consensus download: %0.1fs %s from %s (%s:%d), ' +
  963. 'max download time %0.1fs.', elapsed, status, nickname,
  964. dirip, dirport, max_time)
  965. return download_failed
  966. # does this fallback download the consensus fast enough?
  967. def check_fallback_download_consensus(self):
  968. # include the relay if we're not doing a check, or we can't check (IPv6)
  969. ipv4_failed = False
  970. ipv6_failed = False
  971. if PERFORM_IPV4_DIRPORT_CHECKS:
  972. ipv4_failed = Candidate.fallback_consensus_download_speed(self.dirip,
  973. self.dirport,
  974. self._data['nickname'],
  975. CONSENSUS_DOWNLOAD_SPEED_MAX)
  976. if self.has_ipv6() and PERFORM_IPV6_DIRPORT_CHECKS:
  977. # Clients assume the IPv6 DirPort is the same as the IPv4 DirPort
  978. ipv6_failed = Candidate.fallback_consensus_download_speed(self.ipv6addr,
  979. self.dirport,
  980. self._data['nickname'],
  981. CONSENSUS_DOWNLOAD_SPEED_MAX)
  982. return ((not ipv4_failed) and (not ipv6_failed))
  983. # if this fallback has not passed a download check, try it again,
  984. # and record the result, available in get_fallback_download_consensus
  985. def try_fallback_download_consensus(self):
  986. if not self.get_fallback_download_consensus():
  987. self._data['download_check'] = self.check_fallback_download_consensus()
  988. # did this fallback pass the download check?
  989. def get_fallback_download_consensus(self):
  990. # if we're not performing checks, return True
  991. if not PERFORM_IPV4_DIRPORT_CHECKS and not PERFORM_IPV6_DIRPORT_CHECKS:
  992. return True
  993. # if we are performing checks, but haven't done one, return False
  994. if not self._data.has_key('download_check'):
  995. return False
  996. return self._data['download_check']
  997. # output an optional header comment and info for this fallback
  998. # try_fallback_download_consensus before calling this
  999. def fallbackdir_line(self, fallbacks, prefilter_fallbacks):
  1000. s = ''
  1001. if OUTPUT_COMMENTS:
  1002. s += self.fallbackdir_comment(fallbacks, prefilter_fallbacks)
  1003. # if the download speed is ok, output a C string
  1004. # if it's not, but we OUTPUT_COMMENTS, output a commented-out C string
  1005. if self.get_fallback_download_consensus() or OUTPUT_COMMENTS:
  1006. s += self.fallbackdir_info(self.get_fallback_download_consensus())
  1007. return s
  1008. # output a header comment for this fallback
  1009. def fallbackdir_comment(self, fallbacks, prefilter_fallbacks):
  1010. # /*
  1011. # nickname
  1012. # flags
  1013. # [contact]
  1014. # [identical contact counts]
  1015. # */
  1016. # Multiline C comment
  1017. s = '/*'
  1018. s += '\n'
  1019. s += cleanse_c_multiline_comment(self._data['nickname'])
  1020. s += '\n'
  1021. s += 'Flags: '
  1022. s += cleanse_c_multiline_comment(' '.join(sorted(self._data['flags'])))
  1023. s += '\n'
  1024. if self._data['contact'] is not None:
  1025. s += cleanse_c_multiline_comment(self._data['contact'])
  1026. if CONTACT_COUNT or CONTACT_BLACKLIST_COUNT:
  1027. fallback_count = len([f for f in fallbacks
  1028. if f._data['contact'] == self._data['contact']])
  1029. if fallback_count > 1:
  1030. s += '\n'
  1031. s += '%d identical contacts listed' % (fallback_count)
  1032. if CONTACT_BLACKLIST_COUNT:
  1033. prefilter_count = len([f for f in prefilter_fallbacks
  1034. if f._data['contact'] == self._data['contact']])
  1035. filter_count = prefilter_count - fallback_count
  1036. if filter_count > 0:
  1037. if fallback_count > 1:
  1038. s += ' '
  1039. else:
  1040. s += '\n'
  1041. s += '%d blacklisted' % (filter_count)
  1042. s += '\n'
  1043. s += '*/'
  1044. s += '\n'
  1045. # output the fallback info C string for this fallback
  1046. # this is the text that would go after FallbackDir in a torrc
  1047. # if this relay failed the download test and we OUTPUT_COMMENTS,
  1048. # comment-out the returned string
  1049. def fallbackdir_info(self, dl_speed_ok):
  1050. # "address:dirport orport=port id=fingerprint"
  1051. # "[ipv6=addr:orport]"
  1052. # "weight=FALLBACK_OUTPUT_WEIGHT",
  1053. #
  1054. # Do we want a C string, or a commented-out string?
  1055. c_string = dl_speed_ok
  1056. comment_string = not dl_speed_ok and OUTPUT_COMMENTS
  1057. # If we don't want either kind of string, bail
  1058. if not c_string and not comment_string:
  1059. return ''
  1060. s = ''
  1061. # Comment out the fallback directory entry if it's too slow
  1062. # See the debug output for which address and port is failing
  1063. if comment_string:
  1064. s += '/* Consensus download failed or was too slow:\n'
  1065. # Multi-Line C string with trailing comma (part of a string list)
  1066. # This makes it easier to diff the file, and remove IPv6 lines using grep
  1067. # Integers don't need escaping
  1068. s += '"%s orport=%d id=%s"'%(
  1069. cleanse_c_string(self._data['dir_address']),
  1070. self.orport,
  1071. cleanse_c_string(self._fpr))
  1072. s += '\n'
  1073. if self.has_ipv6():
  1074. s += '" ipv6=%s:%d"'%(cleanse_c_string(self.ipv6addr), self.ipv6orport)
  1075. s += '\n'
  1076. s += '" weight=%d",'%(FALLBACK_OUTPUT_WEIGHT)
  1077. if comment_string:
  1078. s += '\n'
  1079. s += '*/'
  1080. return s
  1081. ## Fallback Candidate List Class
  1082. class CandidateList(dict):
  1083. def __init__(self):
  1084. pass
  1085. def _add_relay(self, details):
  1086. if not 'dir_address' in details: return
  1087. c = Candidate(details)
  1088. self[ c.get_fingerprint() ] = c
  1089. def _add_uptime(self, uptime):
  1090. try:
  1091. fpr = uptime['fingerprint']
  1092. except KeyError:
  1093. raise Exception("Document has no fingerprint field.")
  1094. try:
  1095. c = self[fpr]
  1096. except KeyError:
  1097. logging.debug('Got unknown relay %s in uptime document.'%(fpr,))
  1098. return
  1099. c.add_uptime(uptime)
  1100. def _add_details(self):
  1101. logging.debug('Loading details document.')
  1102. d = fetch('details',
  1103. fields=('fingerprint,nickname,contact,last_changed_address_or_port,' +
  1104. 'consensus_weight,advertised_bandwidth,or_addresses,' +
  1105. 'dir_address,recommended_version,flags,effective_family'))
  1106. logging.debug('Loading details document done.')
  1107. if not 'relays' in d: raise Exception("No relays found in document.")
  1108. for r in d['relays']: self._add_relay(r)
  1109. def _add_uptimes(self):
  1110. logging.debug('Loading uptime document.')
  1111. d = fetch('uptime')
  1112. logging.debug('Loading uptime document done.')
  1113. if not 'relays' in d: raise Exception("No relays found in document.")
  1114. for r in d['relays']: self._add_uptime(r)
  1115. def add_relays(self):
  1116. self._add_details()
  1117. self._add_uptimes()
  1118. def count_guards(self):
  1119. guard_count = 0
  1120. for fpr in self.keys():
  1121. if self[fpr].is_guard():
  1122. guard_count += 1
  1123. return guard_count
  1124. # Find fallbacks that fit the uptime, stability, and flags criteria,
  1125. # and make an array of them in self.fallbacks
  1126. def compute_fallbacks(self):
  1127. self.fallbacks = map(lambda x: self[x],
  1128. filter(lambda x: self[x].is_candidate(),
  1129. self.keys()))
  1130. # sort fallbacks by their consensus weight to advertised bandwidth factor,
  1131. # lowest to highest
  1132. # used to find the median cw_to_bw_factor()
  1133. def sort_fallbacks_by_cw_to_bw_factor(self):
  1134. self.fallbacks.sort(key=lambda f: f.cw_to_bw_factor())
  1135. # sort fallbacks by their measured bandwidth, highest to lowest
  1136. # calculate_measured_bandwidth before calling this
  1137. # this is useful for reviewing candidates in priority order
  1138. def sort_fallbacks_by_measured_bandwidth(self):
  1139. self.fallbacks.sort(key=lambda f: f._data['measured_bandwidth'],
  1140. reverse=True)
  1141. # sort fallbacks by their fingerprint, lowest to highest
  1142. # this is useful for stable diffs of fallback lists
  1143. def sort_fallbacks_by_fingerprint(self):
  1144. self.fallbacks.sort(key=lambda f: f._fpr)
  1145. @staticmethod
  1146. def load_relaylist(file_name):
  1147. """ Read each line in the file, and parse it like a FallbackDir line:
  1148. an IPv4 address and optional port:
  1149. <IPv4 address>:<port>
  1150. which are parsed into dictionary entries:
  1151. ipv4=<IPv4 address>
  1152. dirport=<port>
  1153. followed by a series of key=value entries:
  1154. orport=<port>
  1155. id=<fingerprint>
  1156. ipv6=<IPv6 address>:<IPv6 orport>
  1157. each line's key/value pairs are placed in a dictonary,
  1158. (of string -> string key/value pairs),
  1159. and these dictionaries are placed in an array.
  1160. comments start with # and are ignored """
  1161. relaylist = []
  1162. file_data = read_from_file(file_name, MAX_LIST_FILE_SIZE)
  1163. if file_data is None:
  1164. return relaylist
  1165. for line in file_data.split('\n'):
  1166. relay_entry = {}
  1167. # ignore comments
  1168. line_comment_split = line.split('#')
  1169. line = line_comment_split[0]
  1170. # cleanup whitespace
  1171. line = cleanse_whitespace(line)
  1172. line = line.strip()
  1173. if len(line) == 0:
  1174. continue
  1175. for item in line.split(' '):
  1176. item = item.strip()
  1177. if len(item) == 0:
  1178. continue
  1179. key_value_split = item.split('=')
  1180. kvl = len(key_value_split)
  1181. if kvl < 1 or kvl > 2:
  1182. print '#error Bad %s item: %s, format is key=value.'%(
  1183. file_name, item)
  1184. if kvl == 1:
  1185. # assume that entries without a key are the ipv4 address,
  1186. # perhaps with a dirport
  1187. ipv4_maybe_dirport = key_value_split[0]
  1188. ipv4_maybe_dirport_split = ipv4_maybe_dirport.split(':')
  1189. dirl = len(ipv4_maybe_dirport_split)
  1190. if dirl < 1 or dirl > 2:
  1191. print '#error Bad %s IPv4 item: %s, format is ipv4:port.'%(
  1192. file_name, item)
  1193. if dirl >= 1:
  1194. relay_entry['ipv4'] = ipv4_maybe_dirport_split[0]
  1195. if dirl == 2:
  1196. relay_entry['dirport'] = ipv4_maybe_dirport_split[1]
  1197. elif kvl == 2:
  1198. relay_entry[key_value_split[0]] = key_value_split[1]
  1199. relaylist.append(relay_entry)
  1200. return relaylist
  1201. # apply the fallback whitelist and blacklist
  1202. def apply_filter_lists(self):
  1203. excluded_count = 0
  1204. logging.debug('Applying whitelist and blacklist.')
  1205. # parse the whitelist and blacklist
  1206. whitelist = self.load_relaylist(WHITELIST_FILE_NAME)
  1207. blacklist = self.load_relaylist(BLACKLIST_FILE_NAME)
  1208. filtered_fallbacks = []
  1209. for f in self.fallbacks:
  1210. in_whitelist = f.is_in_whitelist(whitelist)
  1211. in_blacklist = f.is_in_blacklist(blacklist)
  1212. if in_whitelist and in_blacklist:
  1213. if BLACKLIST_EXCLUDES_WHITELIST_ENTRIES:
  1214. # exclude
  1215. excluded_count += 1
  1216. logging.warning('Excluding %s: in both blacklist and whitelist.',
  1217. f._fpr)
  1218. else:
  1219. # include
  1220. filtered_fallbacks.append(f)
  1221. elif in_whitelist:
  1222. # include
  1223. filtered_fallbacks.append(f)
  1224. elif in_blacklist:
  1225. # exclude
  1226. excluded_count += 1
  1227. logging.info('Excluding %s: in blacklist.', f._fpr)
  1228. else:
  1229. if INCLUDE_UNLISTED_ENTRIES:
  1230. # include
  1231. filtered_fallbacks.append(f)
  1232. else:
  1233. # exclude
  1234. excluded_count += 1
  1235. logging.info('Excluding %s: in neither blacklist nor whitelist.',
  1236. f._fpr)
  1237. self.fallbacks = filtered_fallbacks
  1238. return excluded_count
  1239. @staticmethod
  1240. def summarise_filters(initial_count, excluded_count):
  1241. return '/* Whitelist & blacklist excluded %d of %d candidates. */'%(
  1242. excluded_count, initial_count)
  1243. # calculate each fallback's measured bandwidth based on the median
  1244. # consensus weight to advertised bandwdith ratio
  1245. def calculate_measured_bandwidth(self):
  1246. self.sort_fallbacks_by_cw_to_bw_factor()
  1247. median_fallback = self.fallback_median(True)
  1248. median_cw_to_bw_factor = median_fallback.cw_to_bw_factor()
  1249. for f in self.fallbacks:
  1250. f.set_measured_bandwidth(median_cw_to_bw_factor)
  1251. # remove relays with low measured bandwidth from the fallback list
  1252. # calculate_measured_bandwidth for each relay before calling this
  1253. def remove_low_bandwidth_relays(self):
  1254. if MIN_BANDWIDTH is None:
  1255. return
  1256. above_min_bw_fallbacks = []
  1257. for f in self.fallbacks:
  1258. if f._data['measured_bandwidth'] >= MIN_BANDWIDTH:
  1259. above_min_bw_fallbacks.append(f)
  1260. else:
  1261. # the bandwidth we log here is limited by the relay's consensus weight
  1262. # as well as its adverttised bandwidth. See set_measured_bandwidth
  1263. # for details
  1264. logging.info('%s not a candidate: bandwidth %.1fMB/s too low, must ' +
  1265. 'be at least %.1fMB/s', f._fpr,
  1266. f._data['measured_bandwidth']/(1024.0*1024.0),
  1267. MIN_BANDWIDTH/(1024.0*1024.0))
  1268. self.fallbacks = above_min_bw_fallbacks
  1269. # the minimum fallback in the list
  1270. # call one of the sort_fallbacks_* functions before calling this
  1271. def fallback_min(self):
  1272. if len(self.fallbacks) > 0:
  1273. return self.fallbacks[-1]
  1274. else:
  1275. return None
  1276. # the median fallback in the list
  1277. # call one of the sort_fallbacks_* functions before calling this
  1278. def fallback_median(self, require_advertised_bandwidth):
  1279. # use the low-median when there are an evan number of fallbacks,
  1280. # for consistency with the bandwidth authorities
  1281. if len(self.fallbacks) > 0:
  1282. median_position = (len(self.fallbacks) - 1) / 2
  1283. if not require_advertised_bandwidth:
  1284. return self.fallbacks[median_position]
  1285. # if we need advertised_bandwidth but this relay doesn't have it,
  1286. # move to a fallback with greater consensus weight until we find one
  1287. while not self.fallbacks[median_position]._data['advertised_bandwidth']:
  1288. median_position += 1
  1289. if median_position >= len(self.fallbacks):
  1290. return None
  1291. return self.fallbacks[median_position]
  1292. else:
  1293. return None
  1294. # the maximum fallback in the list
  1295. # call one of the sort_fallbacks_* functions before calling this
  1296. def fallback_max(self):
  1297. if len(self.fallbacks) > 0:
  1298. return self.fallbacks[0]
  1299. else:
  1300. return None
  1301. # does exclusion_list contain attribute?
  1302. # if so, return False
  1303. # if not, return True
  1304. # if attribute is None or the empty string, always return True
  1305. @staticmethod
  1306. def allow(attribute, exclusion_list):
  1307. if attribute is None or attribute == '':
  1308. return True
  1309. elif attribute in exclusion_list:
  1310. return False
  1311. else:
  1312. return True
  1313. # make sure there is only one fallback per IPv4 address, and per IPv6 address
  1314. # there is only one IPv4 address on each fallback: the IPv4 DirPort address
  1315. # (we choose the IPv4 ORPort which is on the same IPv4 as the DirPort)
  1316. # there is at most one IPv6 address on each fallback: the IPv6 ORPort address
  1317. # we try to match the IPv4 ORPort, but will use any IPv6 address if needed
  1318. # (clients assume the IPv6 DirPort is the same as the IPv4 DirPort, but
  1319. # typically only use the IPv6 ORPort)
  1320. # if there is no IPv6 address, only the IPv4 address is checked
  1321. # return the number of candidates we excluded
  1322. def limit_fallbacks_same_ip(self):
  1323. ip_limit_fallbacks = []
  1324. ip_list = []
  1325. for f in self.fallbacks:
  1326. if (CandidateList.allow(f.dirip, ip_list)
  1327. and CandidateList.allow(f.ipv6addr, ip_list)):
  1328. ip_limit_fallbacks.append(f)
  1329. ip_list.append(f.dirip)
  1330. if f.has_ipv6():
  1331. ip_list.append(f.ipv6addr)
  1332. elif not CandidateList.allow(f.dirip, ip_list):
  1333. logging.info('Eliminated %s: already have fallback on IPv4 %s'%(
  1334. f._fpr, f.dirip))
  1335. elif f.has_ipv6() and not CandidateList.allow(f.ipv6addr, ip_list):
  1336. logging.info('Eliminated %s: already have fallback on IPv6 %s'%(
  1337. f._fpr, f.ipv6addr))
  1338. original_count = len(self.fallbacks)
  1339. self.fallbacks = ip_limit_fallbacks
  1340. return original_count - len(self.fallbacks)
  1341. # make sure there is only one fallback per ContactInfo
  1342. # if there is no ContactInfo, allow the fallback
  1343. # this check can be gamed by providing no ContactInfo, or by setting the
  1344. # ContactInfo to match another fallback
  1345. # However, given the likelihood that relays with the same ContactInfo will
  1346. # go down at similar times, its usefulness outweighs the risk
  1347. def limit_fallbacks_same_contact(self):
  1348. contact_limit_fallbacks = []
  1349. contact_list = []
  1350. for f in self.fallbacks:
  1351. if CandidateList.allow(f._data['contact'], contact_list):
  1352. contact_limit_fallbacks.append(f)
  1353. contact_list.append(f._data['contact'])
  1354. else:
  1355. logging.info(('Eliminated %s: already have fallback on ' +
  1356. 'ContactInfo %s')%(f._fpr, f._data['contact']))
  1357. original_count = len(self.fallbacks)
  1358. self.fallbacks = contact_limit_fallbacks
  1359. return original_count - len(self.fallbacks)
  1360. # make sure there is only one fallback per effective family
  1361. # if there is no family, allow the fallback
  1362. # this check can't be gamed, because we use effective family, which ensures
  1363. # mutual family declarations
  1364. # if any indirect families exist, the result depends on the order in which
  1365. # fallbacks are sorted in the list
  1366. def limit_fallbacks_same_family(self):
  1367. family_limit_fallbacks = []
  1368. fingerprint_list = []
  1369. for f in self.fallbacks:
  1370. if CandidateList.allow(f._fpr, fingerprint_list):
  1371. family_limit_fallbacks.append(f)
  1372. fingerprint_list.append(f._fpr)
  1373. fingerprint_list.extend(f._data['effective_family'])
  1374. else:
  1375. # technically, we already have a fallback with this fallback in its
  1376. # effective family
  1377. logging.info('Eliminated %s: already have fallback in effective ' +
  1378. 'family'%(f._fpr))
  1379. original_count = len(self.fallbacks)
  1380. self.fallbacks = family_limit_fallbacks
  1381. return original_count - len(self.fallbacks)
  1382. # try a download check on each fallback candidate in order
  1383. # stop after max_count successful downloads
  1384. # but don't remove any candidates from the array
  1385. def try_download_consensus_checks(self, max_count):
  1386. dl_ok_count = 0
  1387. for f in self.fallbacks:
  1388. f.try_fallback_download_consensus()
  1389. if f.get_fallback_download_consensus():
  1390. # this fallback downloaded a consensus ok
  1391. dl_ok_count += 1
  1392. if dl_ok_count >= max_count:
  1393. # we have enough fallbacks
  1394. return
  1395. # put max_count successful candidates in the fallbacks array:
  1396. # - perform download checks on each fallback candidate
  1397. # - retry failed candidates if CONSENSUS_DOWNLOAD_RETRY is set
  1398. # - eliminate failed candidates
  1399. # - if there are more than max_count candidates, eliminate lowest bandwidth
  1400. # - if there are fewer than max_count candidates, leave only successful
  1401. # Return the number of fallbacks that failed the consensus check
  1402. def perform_download_consensus_checks(self, max_count):
  1403. self.sort_fallbacks_by_measured_bandwidth()
  1404. self.try_download_consensus_checks(max_count)
  1405. if CONSENSUS_DOWNLOAD_RETRY:
  1406. # try unsuccessful candidates again
  1407. # we could end up with more than max_count successful candidates here
  1408. self.try_download_consensus_checks(max_count)
  1409. # now we have at least max_count successful candidates,
  1410. # or we've tried them all
  1411. original_count = len(self.fallbacks)
  1412. self.fallbacks = filter(lambda x: x.get_fallback_download_consensus(),
  1413. self.fallbacks)
  1414. # some of these failed the check, others skipped the check,
  1415. # if we already had enough successful downloads
  1416. failed_count = original_count - len(self.fallbacks)
  1417. self.fallbacks = self.fallbacks[:max_count]
  1418. return failed_count
  1419. # return a string that describes a/b as a percentage
  1420. @staticmethod
  1421. def describe_percentage(a, b):
  1422. return '%d/%d = %.0f%%'%(a, b, (a*100.0)/b)
  1423. # return a dictionary of lists of fallbacks by IPv4 netblock
  1424. # the dictionary is keyed by the fingerprint of an arbitrary fallback
  1425. # in each netblock
  1426. # mask_bits is the size of the netblock
  1427. def fallbacks_by_ipv4_netblock(self, mask_bits):
  1428. netblocks = {}
  1429. for f in self.fallbacks:
  1430. found_netblock = False
  1431. for b in netblocks.keys():
  1432. # we found an existing netblock containing this fallback
  1433. if f.ipv4_netblocks_equal(self[b], mask_bits):
  1434. # add it to the list
  1435. netblocks[b].append(f)
  1436. found_netblock = True
  1437. break
  1438. # make a new netblock based on this fallback's fingerprint
  1439. if not found_netblock:
  1440. netblocks[f._fpr] = [f]
  1441. return netblocks
  1442. # return a dictionary of lists of fallbacks by IPv6 netblock
  1443. # where mask_bits is the size of the netblock
  1444. def fallbacks_by_ipv6_netblock(self, mask_bits):
  1445. netblocks = {}
  1446. for f in self.fallbacks:
  1447. # skip fallbacks without IPv6 addresses
  1448. if not f.has_ipv6():
  1449. continue
  1450. found_netblock = False
  1451. for b in netblocks.keys():
  1452. # we found an existing netblock containing this fallback
  1453. if f.ipv6_netblocks_equal(self[b], mask_bits):
  1454. # add it to the list
  1455. netblocks[b].append(f)
  1456. found_netblock = True
  1457. break
  1458. # make a new netblock based on this fallback's fingerprint
  1459. if not found_netblock:
  1460. netblocks[f._fpr] = [f]
  1461. return netblocks
  1462. # log a message about the proportion of fallbacks in each IPv4 netblock,
  1463. # where mask_bits is the size of the netblock
  1464. def describe_fallback_ipv4_netblock_mask(self, mask_bits):
  1465. fallback_count = len(self.fallbacks)
  1466. shared_netblock_fallback_count = 0
  1467. most_frequent_netblock = None
  1468. netblocks = self.fallbacks_by_ipv4_netblock(mask_bits)
  1469. for b in netblocks.keys():
  1470. if len(netblocks[b]) > 1:
  1471. # how many fallbacks are in a netblock with other fallbacks?
  1472. shared_netblock_fallback_count += len(netblocks[b])
  1473. # what's the netblock with the most fallbacks?
  1474. if (most_frequent_netblock is None
  1475. or len(netblocks[b]) > len(netblocks[most_frequent_netblock])):
  1476. most_frequent_netblock = b
  1477. logging.debug('Fallback IPv4 addresses in the same /%d:'%(mask_bits))
  1478. for f in netblocks[b]:
  1479. logging.debug('%s - %s', f.dirip, f._fpr)
  1480. if most_frequent_netblock is not None:
  1481. logging.warning('There are %s fallbacks in the IPv4 /%d containing %s'%(
  1482. CandidateList.describe_percentage(
  1483. len(netblocks[most_frequent_netblock]),
  1484. fallback_count),
  1485. mask_bits,
  1486. self[most_frequent_netblock].dirip))
  1487. if shared_netblock_fallback_count > 0:
  1488. logging.warning(('%s of fallbacks are in an IPv4 /%d with other ' +
  1489. 'fallbacks')%(CandidateList.describe_percentage(
  1490. shared_netblock_fallback_count,
  1491. fallback_count),
  1492. mask_bits))
  1493. # log a message about the proportion of fallbacks in each IPv6 netblock,
  1494. # where mask_bits is the size of the netblock
  1495. def describe_fallback_ipv6_netblock_mask(self, mask_bits):
  1496. fallback_count = len(self.fallbacks_with_ipv6())
  1497. shared_netblock_fallback_count = 0
  1498. most_frequent_netblock = None
  1499. netblocks = self.fallbacks_by_ipv6_netblock(mask_bits)
  1500. for b in netblocks.keys():
  1501. if len(netblocks[b]) > 1:
  1502. # how many fallbacks are in a netblock with other fallbacks?
  1503. shared_netblock_fallback_count += len(netblocks[b])
  1504. # what's the netblock with the most fallbacks?
  1505. if (most_frequent_netblock is None
  1506. or len(netblocks[b]) > len(netblocks[most_frequent_netblock])):
  1507. most_frequent_netblock = b
  1508. logging.debug('Fallback IPv6 addresses in the same /%d:'%(mask_bits))
  1509. for f in netblocks[b]:
  1510. logging.debug('%s - %s', f.ipv6addr, f._fpr)
  1511. if most_frequent_netblock is not None:
  1512. logging.warning('There are %s fallbacks in the IPv6 /%d containing %s'%(
  1513. CandidateList.describe_percentage(
  1514. len(netblocks[most_frequent_netblock]),
  1515. fallback_count),
  1516. mask_bits,
  1517. self[most_frequent_netblock].ipv6addr))
  1518. if shared_netblock_fallback_count > 0:
  1519. logging.warning(('%s of fallbacks are in an IPv6 /%d with other ' +
  1520. 'fallbacks')%(CandidateList.describe_percentage(
  1521. shared_netblock_fallback_count,
  1522. fallback_count),
  1523. mask_bits))
  1524. # log a message about the proportion of fallbacks in each IPv4 /8, /16,
  1525. # and /24
  1526. def describe_fallback_ipv4_netblocks(self):
  1527. # this doesn't actually tell us anything useful
  1528. #self.describe_fallback_ipv4_netblock_mask(8)
  1529. self.describe_fallback_ipv4_netblock_mask(16)
  1530. self.describe_fallback_ipv4_netblock_mask(24)
  1531. # log a message about the proportion of fallbacks in each IPv6 /12 (RIR),
  1532. # /23 (smaller RIR blocks), /32 (LIR), /48 (Customer), and /64 (Host)
  1533. # https://www.iana.org/assignments/ipv6-unicast-address-assignments/
  1534. def describe_fallback_ipv6_netblocks(self):
  1535. # these don't actually tell us anything useful
  1536. #self.describe_fallback_ipv6_netblock_mask(12)
  1537. #self.describe_fallback_ipv6_netblock_mask(23)
  1538. self.describe_fallback_ipv6_netblock_mask(32)
  1539. self.describe_fallback_ipv6_netblock_mask(48)
  1540. self.describe_fallback_ipv6_netblock_mask(64)
  1541. # log a message about the proportion of fallbacks in each IPv4 and IPv6
  1542. # netblock
  1543. def describe_fallback_netblocks(self):
  1544. self.describe_fallback_ipv4_netblocks()
  1545. self.describe_fallback_ipv6_netblocks()
  1546. # return a list of fallbacks which are on the IPv4 ORPort port
  1547. def fallbacks_on_ipv4_orport(self, port):
  1548. return filter(lambda x: x.orport == port, self.fallbacks)
  1549. # return a list of fallbacks which are on the IPv6 ORPort port
  1550. def fallbacks_on_ipv6_orport(self, port):
  1551. return filter(lambda x: x.ipv6orport == port, self.fallbacks_with_ipv6())
  1552. # return a list of fallbacks which are on the DirPort port
  1553. def fallbacks_on_dirport(self, port):
  1554. return filter(lambda x: x.dirport == port, self.fallbacks)
  1555. # log a message about the proportion of fallbacks on IPv4 ORPort port
  1556. # and return that count
  1557. def describe_fallback_ipv4_orport(self, port):
  1558. port_count = len(self.fallbacks_on_ipv4_orport(port))
  1559. fallback_count = len(self.fallbacks)
  1560. logging.warning('%s of fallbacks are on IPv4 ORPort %d'%(
  1561. CandidateList.describe_percentage(port_count,
  1562. fallback_count),
  1563. port))
  1564. return port_count
  1565. # log a message about the proportion of IPv6 fallbacks on IPv6 ORPort port
  1566. # and return that count
  1567. def describe_fallback_ipv6_orport(self, port):
  1568. port_count = len(self.fallbacks_on_ipv6_orport(port))
  1569. fallback_count = len(self.fallbacks_with_ipv6())
  1570. logging.warning('%s of IPv6 fallbacks are on IPv6 ORPort %d'%(
  1571. CandidateList.describe_percentage(port_count,
  1572. fallback_count),
  1573. port))
  1574. return port_count
  1575. # log a message about the proportion of fallbacks on DirPort port
  1576. # and return that count
  1577. def describe_fallback_dirport(self, port):
  1578. port_count = len(self.fallbacks_on_dirport(port))
  1579. fallback_count = len(self.fallbacks)
  1580. logging.warning('%s of fallbacks are on DirPort %d'%(
  1581. CandidateList.describe_percentage(port_count,
  1582. fallback_count),
  1583. port))
  1584. return port_count
  1585. # log a message about the proportion of fallbacks on each dirport,
  1586. # each IPv4 orport, and each IPv6 orport
  1587. def describe_fallback_ports(self):
  1588. fallback_count = len(self.fallbacks)
  1589. ipv4_or_count = fallback_count
  1590. ipv4_or_count -= self.describe_fallback_ipv4_orport(443)
  1591. ipv4_or_count -= self.describe_fallback_ipv4_orport(9001)
  1592. logging.warning('%s of fallbacks are on other IPv4 ORPorts'%(
  1593. CandidateList.describe_percentage(ipv4_or_count,
  1594. fallback_count)))
  1595. ipv6_fallback_count = len(self.fallbacks_with_ipv6())
  1596. ipv6_or_count = ipv6_fallback_count
  1597. ipv6_or_count -= self.describe_fallback_ipv6_orport(443)
  1598. ipv6_or_count -= self.describe_fallback_ipv6_orport(9001)
  1599. logging.warning('%s of IPv6 fallbacks are on other IPv6 ORPorts'%(
  1600. CandidateList.describe_percentage(ipv6_or_count,
  1601. ipv6_fallback_count)))
  1602. dir_count = fallback_count
  1603. dir_count -= self.describe_fallback_dirport(80)
  1604. dir_count -= self.describe_fallback_dirport(9030)
  1605. logging.warning('%s of fallbacks are on other DirPorts'%(
  1606. CandidateList.describe_percentage(dir_count,
  1607. fallback_count)))
  1608. # return a list of fallbacks which have the Exit flag
  1609. def fallbacks_with_exit(self):
  1610. return filter(lambda x: x.is_exit(), self.fallbacks)
  1611. # log a message about the proportion of fallbacks with an Exit flag
  1612. def describe_fallback_exit_flag(self):
  1613. exit_falback_count = len(self.fallbacks_with_exit())
  1614. fallback_count = len(self.fallbacks)
  1615. logging.warning('%s of fallbacks have the Exit flag'%(
  1616. CandidateList.describe_percentage(exit_falback_count,
  1617. fallback_count)))
  1618. # return a list of fallbacks which have an IPv6 address
  1619. def fallbacks_with_ipv6(self):
  1620. return filter(lambda x: x.has_ipv6(), self.fallbacks)
  1621. # log a message about the proportion of fallbacks on IPv6
  1622. def describe_fallback_ip_family(self):
  1623. ipv6_falback_count = len(self.fallbacks_with_ipv6())
  1624. fallback_count = len(self.fallbacks)
  1625. logging.warning('%s of fallbacks are on IPv6'%(
  1626. CandidateList.describe_percentage(ipv6_falback_count,
  1627. fallback_count)))
  1628. def summarise_fallbacks(self, eligible_count, operator_count, failed_count,
  1629. guard_count, target_count):
  1630. # Report:
  1631. # whether we checked consensus download times
  1632. # the number of fallback directories (and limits/exclusions, if relevant)
  1633. # min & max fallback bandwidths
  1634. # #error if below minimum count
  1635. if PERFORM_IPV4_DIRPORT_CHECKS or PERFORM_IPV6_DIRPORT_CHECKS:
  1636. s = '/* Checked %s%s%s DirPorts served a consensus within %.1fs. */'%(
  1637. 'IPv4' if PERFORM_IPV4_DIRPORT_CHECKS else '',
  1638. ' and ' if (PERFORM_IPV4_DIRPORT_CHECKS
  1639. and PERFORM_IPV6_DIRPORT_CHECKS) else '',
  1640. 'IPv6' if PERFORM_IPV6_DIRPORT_CHECKS else '',
  1641. CONSENSUS_DOWNLOAD_SPEED_MAX)
  1642. else:
  1643. s = '/* Did not check IPv4 or IPv6 DirPort consensus downloads. */'
  1644. s += '\n'
  1645. # Multiline C comment with #error if things go bad
  1646. s += '/*'
  1647. s += '\n'
  1648. # Integers don't need escaping in C comments
  1649. fallback_count = len(self.fallbacks)
  1650. if FALLBACK_PROPORTION_OF_GUARDS is None:
  1651. fallback_proportion = ''
  1652. else:
  1653. fallback_proportion = ', Target %d (%d * %.2f)'%(target_count,
  1654. guard_count,
  1655. FALLBACK_PROPORTION_OF_GUARDS)
  1656. s += 'Final Count: %d (Eligible %d%s'%(fallback_count, eligible_count,
  1657. fallback_proportion)
  1658. if MAX_FALLBACK_COUNT is not None:
  1659. s += ', Max %d'%(MAX_FALLBACK_COUNT)
  1660. s += ')\n'
  1661. if eligible_count != fallback_count:
  1662. removed_count = eligible_count - fallback_count
  1663. excess_to_target_or_max = (eligible_count - operator_count - failed_count
  1664. - fallback_count)
  1665. # some 'Failed' failed the check, others 'Skipped' the check,
  1666. # if we already had enough successful downloads
  1667. s += ('Excluded: %d (Same Operator %d, Failed/Skipped Download %d, ' +
  1668. 'Excess %d)')%(removed_count, operator_count, failed_count,
  1669. excess_to_target_or_max)
  1670. s += '\n'
  1671. min_fb = self.fallback_min()
  1672. min_bw = min_fb._data['measured_bandwidth']
  1673. max_fb = self.fallback_max()
  1674. max_bw = max_fb._data['measured_bandwidth']
  1675. s += 'Bandwidth Range: %.1f - %.1f MB/s'%(min_bw/(1024.0*1024.0),
  1676. max_bw/(1024.0*1024.0))
  1677. s += '\n'
  1678. s += '*/'
  1679. if fallback_count < MIN_FALLBACK_COUNT:
  1680. # We must have a minimum number of fallbacks so they are always
  1681. # reachable, and are in diverse locations
  1682. s += '\n'
  1683. s += '#error Fallback Count %d is too low. '%(fallback_count)
  1684. s += 'Must be at least %d for diversity. '%(MIN_FALLBACK_COUNT)
  1685. s += 'Try adding entries to the whitelist, '
  1686. s += 'or setting INCLUDE_UNLISTED_ENTRIES = True.'
  1687. return s
  1688. ## Main Function
  1689. def list_fallbacks():
  1690. """ Fetches required onionoo documents and evaluates the
  1691. fallback directory criteria for each of the relays """
  1692. logging.warning('Downloading and parsing Onionoo data. ' +
  1693. 'This may take some time.')
  1694. # find relays that could be fallbacks
  1695. candidates = CandidateList()
  1696. candidates.add_relays()
  1697. # work out how many fallbacks we want
  1698. guard_count = candidates.count_guards()
  1699. if FALLBACK_PROPORTION_OF_GUARDS is None:
  1700. target_count = guard_count
  1701. else:
  1702. target_count = int(guard_count * FALLBACK_PROPORTION_OF_GUARDS)
  1703. # the maximum number of fallbacks is the least of:
  1704. # - the target fallback count (FALLBACK_PROPORTION_OF_GUARDS * guard count)
  1705. # - the maximum fallback count (MAX_FALLBACK_COUNT)
  1706. if MAX_FALLBACK_COUNT is None:
  1707. max_count = target_count
  1708. else:
  1709. max_count = min(target_count, MAX_FALLBACK_COUNT)
  1710. candidates.compute_fallbacks()
  1711. prefilter_fallbacks = copy.copy(candidates.fallbacks)
  1712. # filter with the whitelist and blacklist
  1713. initial_count = len(candidates.fallbacks)
  1714. excluded_count = candidates.apply_filter_lists()
  1715. print candidates.summarise_filters(initial_count, excluded_count)
  1716. eligible_count = len(candidates.fallbacks)
  1717. # calculate the measured bandwidth of each relay,
  1718. # then remove low-bandwidth relays
  1719. candidates.calculate_measured_bandwidth()
  1720. candidates.remove_low_bandwidth_relays()
  1721. # print the raw fallback list
  1722. #for x in candidates.fallbacks:
  1723. # print x.fallbackdir_line(True)
  1724. # print json.dumps(candidates[x]._data, sort_keys=True, indent=4,
  1725. # separators=(',', ': '), default=json_util.default)
  1726. # impose mandatory conditions here, like one per contact, family, IP
  1727. # in measured bandwidth order
  1728. candidates.sort_fallbacks_by_measured_bandwidth()
  1729. operator_count = 0
  1730. # only impose these limits on the final list - operators can nominate
  1731. # multiple candidate fallbacks, and then we choose the best set
  1732. if not OUTPUT_CANDIDATES:
  1733. operator_count += candidates.limit_fallbacks_same_ip()
  1734. operator_count += candidates.limit_fallbacks_same_contact()
  1735. operator_count += candidates.limit_fallbacks_same_family()
  1736. # check if each candidate can serve a consensus
  1737. # there's a small risk we've eliminated relays from the same operator that
  1738. # can serve a consensus, in favour of one that can't
  1739. # but given it takes up to 15 seconds to check each consensus download,
  1740. # the risk is worth it
  1741. if PERFORM_IPV4_DIRPORT_CHECKS or PERFORM_IPV6_DIRPORT_CHECKS:
  1742. logging.warning('Checking consensus download speeds. ' +
  1743. 'This may take some time.')
  1744. failed_count = candidates.perform_download_consensus_checks(max_count)
  1745. # analyse and log interesting diversity metrics
  1746. # like netblock, ports, exit, IPv4-only
  1747. # (we can't easily analyse AS, and it's hard to accurately analyse country)
  1748. candidates.describe_fallback_ip_family()
  1749. # if we can't import the ipaddress module, we can't do netblock analysis
  1750. if HAVE_IPADDRESS:
  1751. candidates.describe_fallback_netblocks()
  1752. candidates.describe_fallback_ports()
  1753. candidates.describe_fallback_exit_flag()
  1754. # output C comments summarising the fallback selection process
  1755. if len(candidates.fallbacks) > 0:
  1756. print candidates.summarise_fallbacks(eligible_count, operator_count,
  1757. failed_count, guard_count,
  1758. target_count)
  1759. else:
  1760. print '/* No Fallbacks met criteria */'
  1761. # output C comments specifying the OnionOO data used to create the list
  1762. for s in fetch_source_list():
  1763. print describe_fetch_source(s)
  1764. # if we're outputting the final fallback list, sort by fingerprint
  1765. # this makes diffs much more stable
  1766. # otherwise, leave sorted by bandwidth, which allows operators to be
  1767. # contacted in priority order
  1768. if not OUTPUT_CANDIDATES:
  1769. candidates.sort_fallbacks_by_fingerprint()
  1770. for x in candidates.fallbacks:
  1771. print x.fallbackdir_line(candidates.fallbacks, prefilter_fallbacks)
  1772. if __name__ == "__main__":
  1773. list_fallbacks()