commit 3f885fe071decd80da7e1538dbbfdd31ae3a76fa Author: Karsten Loesing karsten.loesing@gmx.net Date: Mon Aug 27 08:16:34 2012 +0200

Add mostly unmodified version of Mike's HotPETs 2009 report. --- 2009/torflow/.gitignore | 3 + 2009/torflow/0-93-100000-buildtimes-res100.pdf | Bin 0 -> 25847 bytes 2009/torflow/BadNodes.pdf | Bin 0 -> 17164 bytes 2009/torflow/BadNodesWin.pdf | Bin 0 -> 17397 bytes 2009/torflow/CircFailure-BwLimit2.pdf | Bin 0 -> 18145 bytes 2009/torflow/CircFailure-LimitWin.pdf | Bin 0 -> 18559 bytes 2009/torflow/CircFailure-Win2.pdf | Bin 0 -> 17851 bytes 2009/torflow/CircFailure-WinLimit.pdf | Bin 0 -> 18360 bytes 2009/torflow/CircFailure-WinMid.pdf | Bin 0 -> 17170 bytes 2009/torflow/CircFailure.pdf | Bin 0 -> 19099 bytes 2009/torflow/CircFailure2.pdf | Bin 0 -> 22478 bytes 2009/torflow/ControlPort2.pdf | Bin 0 -> 18870 bytes 2009/torflow/Extends-BwLimit2.pdf | Bin 0 -> 17849 bytes 2009/torflow/ExtendsBar.pdf | Bin 0 -> 17512 bytes 2009/torflow/ExtendsBar2.pdf | Bin 0 -> 19336 bytes 2009/torflow/PathSupport.pdf | Bin 0 -> 9994 bytes 2009/torflow/StreamBwBar2.pdf | Bin 0 -> 19436 bytes 2009/torflow/llncs.cls | 1016 ++++++++++++++++++++++++ 2009/torflow/torflow.bib | 150 ++++ 2009/torflow/torflow.tex | 713 +++++++++++++++++ 2009/torflow/usenix.sty | 96 +++ 21 files changed, 1978 insertions(+), 0 deletions(-)

diff --git a/2009/torflow/.gitignore b/2009/torflow/.gitignore new file mode 100644 index 0000000..afd7e8c --- /dev/null +++ b/2009/torflow/.gitignore @@ -0,0 +1,3 @@ +torflow.pdf +torflow-2009-08-07.pdf + diff --git a/2009/torflow/0-93-100000-buildtimes-res100.pdf b/2009/torflow/0-93-100000-buildtimes-res100.pdf new file mode 100644 index 0000000..ae97316 Binary files /dev/null and b/2009/torflow/0-93-100000-buildtimes-res100.pdf differ diff --git a/2009/torflow/BadNodes.pdf b/2009/torflow/BadNodes.pdf new file mode 100644 index 0000000..3e6f56d Binary files /dev/null and b/2009/torflow/BadNodes.pdf differ diff --git a/2009/torflow/BadNodesWin.pdf b/2009/torflow/BadNodesWin.pdf new file mode 100644 index 0000000..e7aa5d0 Binary files /dev/null and b/2009/torflow/BadNodesWin.pdf differ diff --git a/2009/torflow/CircFailure-BwLimit2.pdf b/2009/torflow/CircFailure-BwLimit2.pdf new file mode 100644 index 0000000..70c729e Binary files /dev/null and b/2009/torflow/CircFailure-BwLimit2.pdf differ diff --git a/2009/torflow/CircFailure-LimitWin.pdf b/2009/torflow/CircFailure-LimitWin.pdf new file mode 100644 index 0000000..ff25ab3 Binary files /dev/null and b/2009/torflow/CircFailure-LimitWin.pdf differ diff --git a/2009/torflow/CircFailure-Win2.pdf b/2009/torflow/CircFailure-Win2.pdf new file mode 100644 index 0000000..c7b0e4e Binary files /dev/null and b/2009/torflow/CircFailure-Win2.pdf differ diff --git a/2009/torflow/CircFailure-WinLimit.pdf b/2009/torflow/CircFailure-WinLimit.pdf new file mode 100644 index 0000000..f59ae32 Binary files /dev/null and b/2009/torflow/CircFailure-WinLimit.pdf differ diff --git a/2009/torflow/CircFailure-WinMid.pdf b/2009/torflow/CircFailure-WinMid.pdf new file mode 100644 index 0000000..e320c17 Binary files /dev/null and b/2009/torflow/CircFailure-WinMid.pdf differ diff --git a/2009/torflow/CircFailure.pdf b/2009/torflow/CircFailure.pdf new file mode 100644 index 0000000..992c04b Binary files /dev/null and b/2009/torflow/CircFailure.pdf differ diff --git a/2009/torflow/CircFailure2.pdf b/2009/torflow/CircFailure2.pdf new file mode 100644 index 0000000..feb32b4 Binary files /dev/null and b/2009/torflow/CircFailure2.pdf differ diff --git a/2009/torflow/ControlPort2.pdf b/2009/torflow/ControlPort2.pdf new file mode 100644 index 0000000..2185ee5 Binary files /dev/null and b/2009/torflow/ControlPort2.pdf differ diff --git a/2009/torflow/Extends-BwLimit2.pdf b/2009/torflow/Extends-BwLimit2.pdf new file mode 100644 index 0000000..bc7b0c7 Binary files /dev/null and b/2009/torflow/Extends-BwLimit2.pdf differ diff --git a/2009/torflow/ExtendsBar.pdf b/2009/torflow/ExtendsBar.pdf new file mode 100644 index 0000000..184ab47 Binary files /dev/null and b/2009/torflow/ExtendsBar.pdf differ diff --git a/2009/torflow/ExtendsBar2.pdf b/2009/torflow/ExtendsBar2.pdf new file mode 100644 index 0000000..f8b44a1 Binary files /dev/null and b/2009/torflow/ExtendsBar2.pdf differ diff --git a/2009/torflow/PathSupport.pdf b/2009/torflow/PathSupport.pdf new file mode 100644 index 0000000..9b7f877 Binary files /dev/null and b/2009/torflow/PathSupport.pdf differ diff --git a/2009/torflow/StreamBwBar2.pdf b/2009/torflow/StreamBwBar2.pdf new file mode 100644 index 0000000..2848786 Binary files /dev/null and b/2009/torflow/StreamBwBar2.pdf differ diff --git a/2009/torflow/llncs.cls b/2009/torflow/llncs.cls new file mode 100644 index 0000000..697dd77 --- /dev/null +++ b/2009/torflow/llncs.cls @@ -0,0 +1,1016 @@ +% LLNCS DOCUMENT CLASS -- version 2.8 +% for LaTeX2e +% +\NeedsTeXFormat{LaTeX2e}[1995/12/01] +\ProvidesClass{llncs}[2000/05/16 v2.8 +^^JLaTeX document class for Lecture Notes in Computer Science] +% Options +\let\if@envcntreset\iffalse +\DeclareOption{envcountreset}{\let\if@envcntreset\iftrue} +\DeclareOption{citeauthoryear}{\let\citeauthoryear=Y} +\DeclareOption{oribibl}{\let\oribibl=Y} +\let\if@custvec\iftrue +\DeclareOption{orivec}{\let\if@custvec\iffalse} +\let\if@envcntsame\iffalse +\DeclareOption{envcountsame}{\let\if@envcntsame\iftrue} +\let\if@envcntsect\iffalse +\DeclareOption{envcountsect}{\let\if@envcntsect\iftrue} +\let\if@runhead\iffalse +\DeclareOption{runningheads}{\let\if@runhead\iftrue} + +\let\if@openbib\iffalse +\DeclareOption{openbib}{\let\if@openbib\iftrue} + +\DeclareOption*{\PassOptionsToClass{\CurrentOption}{article}} + +\ProcessOptions + +\LoadClass[twoside]{article} +\RequirePackage{multicol} % needed for the list of participants, index + +\setlength{\textwidth}{12.2cm} +\setlength{\textheight}{19.3cm} + +% Ragged bottom for the actual page +\def\thisbottomragged{\def@textbottom{\vskip\z@ plus.0001fil +\global\let@textbottom\relax}} + +\renewcommand\small{% + @setfontsize\small@ixpt{11}% + \abovedisplayskip 8.5\p@ @plus3\p@ @minus4\p@ + \abovedisplayshortskip \z@ @plus2\p@ + \belowdisplayshortskip 4\p@ @plus2\p@ @minus2\p@ + \def@listi{\leftmargin\leftmargini + \parsep 0\p@ @plus1\p@ @minus\p@ + \topsep 8\p@ @plus2\p@ @minus4\p@ + \itemsep0\p@}% + \belowdisplayskip \abovedisplayskip +} + +\frenchspacing +\widowpenalty=10000 +\clubpenalty=10000 + +\setlength\oddsidemargin {63\p@} +\setlength\evensidemargin {63\p@} +\setlength\marginparwidth {90\p@} + +\setlength\headsep {16\p@} + +\setlength\footnotesep{7.7\p@} +\setlength\textfloatsep{8mm@plus 2\p@ @minus 4\p@} +\setlength\intextsep {8mm@plus 2\p@ @minus 2\p@} + +\setcounter{secnumdepth}{2} + +\newcounter {chapter} +\renewcommand\thechapter {@arabic\c@chapter} + +\newif\if@mainmatter @mainmattertrue +\newcommand\frontmatter{\cleardoublepage + @mainmatterfalse\pagenumbering{Roman}} +\newcommand\mainmatter{\cleardoublepage + @mainmattertrue\pagenumbering{arabic}} +\newcommand\backmatter{\if@openright\cleardoublepage\else\clearpage\fi + @mainmatterfalse} + +\renewcommand\part{\cleardoublepage + \thispagestyle{empty}% + \if@twocolumn + \onecolumn + @tempswatrue + \else + @tempswafalse + \fi + \null\vfil + \secdef@part@spart} + +\def@part[#1]#2{% + \ifnum \c@secnumdepth >-2\relax + \refstepcounter{part}% + \addcontentsline{toc}{part}{\thepart\hspace{1em}#1}% + \else + \addcontentsline{toc}{part}{#1}% + \fi + \markboth{}{}% + {\centering + \interlinepenalty @M + \normalfont + \ifnum \c@secnumdepth >-2\relax + \huge\bfseries \partname~\thepart + \par + \vskip 20\p@ + \fi + \Huge \bfseries #2\par}% + @endpart} +\def@spart#1{% + {\centering + \interlinepenalty @M + \normalfont + \Huge \bfseries #1\par}% + @endpart} +\def@endpart{\vfil\newpage + \if@twoside + \null + \thispagestyle{empty}% + \newpage + \fi + \if@tempswa + \twocolumn + \fi} + +\newcommand\chapter{\clearpage + \thispagestyle{empty}% + \global@topnum\z@ + @afterindentfalse + \secdef@chapter@schapter} +\def@chapter[#1]#2{\ifnum \c@secnumdepth >\m@ne + \if@mainmatter + \refstepcounter{chapter}% + \typeout{@chapapp\space\thechapter.}% + \addcontentsline{toc}{chapter}% + {\protect\numberline{\thechapter}#1}% + \else + \addcontentsline{toc}{chapter}{#1}% + \fi + \else + \addcontentsline{toc}{chapter}{#1}% + \fi + \chaptermark{#1}% + \addtocontents{lof}{\protect\addvspace{10\p@}}% + \addtocontents{lot}{\protect\addvspace{10\p@}}% + \if@twocolumn + @topnewpage[@makechapterhead{#2}]% + \else + @makechapterhead{#2}% + @afterheading + \fi} +\def@makechapterhead#1{% +% \vspace*{50\p@}% + {\centering + \ifnum \c@secnumdepth >\m@ne + \if@mainmatter + \large\bfseries @chapapp{} \thechapter + \par\nobreak + \vskip 20\p@ + \fi + \fi + \interlinepenalty@M + \Large \bfseries #1\par\nobreak + \vskip 40\p@ + }} +\def@schapter#1{\if@twocolumn + @topnewpage[@makeschapterhead{#1}]% + \else + @makeschapterhead{#1}% + @afterheading + \fi} +\def@makeschapterhead#1{% +% \vspace*{50\p@}% + {\centering + \normalfont + \interlinepenalty@M + \Large \bfseries #1\par\nobreak + \vskip 40\p@ + }} + +\renewcommand\section{@startsection{section}{1}{\z@}% + {-18\p@ @plus -4\p@ @minus -4\p@}% + {12\p@ @plus 4\p@ @minus 4\p@}% + {\normalfont\large\bfseries\boldmath + \rightskip=\z@ @plus 8em\pretolerance=10000 }} +\renewcommand\subsection{@startsection{subsection}{2}{\z@}% + {-18\p@ @plus -4\p@ @minus -4\p@}% + {8\p@ @plus 4\p@ @minus 4\p@}% + {\normalfont\normalsize\bfseries\boldmath + \rightskip=\z@ @plus 8em\pretolerance=10000 }} +\renewcommand\subsubsection{@startsection{subsubsection}{3}{\z@}% + {-18\p@ @plus -4\p@ @minus -4\p@}% + {-0.5em @plus -0.22em @minus -0.1em}% + {\normalfont\normalsize\bfseries\boldmath}} +\renewcommand\paragraph{@startsection{paragraph}{4}{\z@}% + {-12\p@ @plus -4\p@ @minus -4\p@}% + {-0.5em @plus -0.22em @minus -0.1em}% + {\normalfont\normalsize\itshape}} +\renewcommand\subparagraph[1]{\typeout{LLNCS warning: You should not use + \string\subparagraph\space with this class}\vskip0.5cm +You should not use \verb|\subparagraph| with this class.\vskip0.5cm} + +\DeclareMathSymbol{\Gamma}{\mathalpha}{letters}{"00} +\DeclareMathSymbol{\Delta}{\mathalpha}{letters}{"01} +\DeclareMathSymbol{\Theta}{\mathalpha}{letters}{"02} +\DeclareMathSymbol{\Lambda}{\mathalpha}{letters}{"03} +\DeclareMathSymbol{\Xi}{\mathalpha}{letters}{"04} +\DeclareMathSymbol{\Pi}{\mathalpha}{letters}{"05} +\DeclareMathSymbol{\Sigma}{\mathalpha}{letters}{"06} +\DeclareMathSymbol{\Upsilon}{\mathalpha}{letters}{"07} +\DeclareMathSymbol{\Phi}{\mathalpha}{letters}{"08} +\DeclareMathSymbol{\Psi}{\mathalpha}{letters}{"09} +\DeclareMathSymbol{\Omega}{\mathalpha}{letters}{"0A} + +\let\footnotesize\small + +\if@custvec +\def\vec#1{\mathchoice{\mbox{\boldmath$\displaystyle#1$}} +{\mbox{\boldmath$\textstyle#1$}} +{\mbox{\boldmath$\scriptstyle#1$}} +{\mbox{\boldmath$\scriptscriptstyle#1$}}} +\fi + +\def\squareforqed{\hbox{\rlap{$\sqcap$}$\sqcup$}} +\def\qed{\ifmmode\squareforqed\else{\unskip\nobreak\hfil +\penalty50\hskip1em\null\nobreak\hfil\squareforqed +\parfillskip=0pt\finalhyphendemerits=0\endgraf}\fi} + +\def\getsto{\mathrel{\mathchoice {\vcenter{\offinterlineskip +\halign{\hfil +$\displaystyle##$\hfil\cr\gets\cr\to\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\textstyle##$\hfil\cr\gets +\cr\to\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\scriptstyle##$\hfil\cr\gets +\cr\to\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\scriptscriptstyle##$\hfil\cr +\gets\cr\to\cr}}}}} +\def\lid{\mathrel{\mathchoice {\vcenter{\offinterlineskip\halign{\hfil +$\displaystyle##$\hfil\cr<\cr\noalign{\vskip1.2pt}=\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\textstyle##$\hfil\cr<\cr +\noalign{\vskip1.2pt}=\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\scriptstyle##$\hfil\cr<\cr +\noalign{\vskip1pt}=\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\scriptscriptstyle##$\hfil\cr +<\cr +\noalign{\vskip0.9pt}=\cr}}}}} +\def\gid{\mathrel{\mathchoice {\vcenter{\offinterlineskip\halign{\hfil +$\displaystyle##$\hfil\cr>\cr\noalign{\vskip1.2pt}=\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\textstyle##$\hfil\cr>\cr +\noalign{\vskip1.2pt}=\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\scriptstyle##$\hfil\cr>\cr +\noalign{\vskip1pt}=\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\scriptscriptstyle##$\hfil\cr +>\cr +\noalign{\vskip0.9pt}=\cr}}}}} +\def\grole{\mathrel{\mathchoice {\vcenter{\offinterlineskip +\halign{\hfil +$\displaystyle##$\hfil\cr>\cr\noalign{\vskip-1pt}<\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\textstyle##$\hfil\cr +>\cr\noalign{\vskip-1pt}<\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\scriptstyle##$\hfil\cr +>\cr\noalign{\vskip-0.8pt}<\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\scriptscriptstyle##$\hfil\cr +>\cr\noalign{\vskip-0.3pt}<\cr}}}}} +\def\bbbr{{\rm I!R}} %reelle Zahlen +\def\bbbm{{\rm I!M}} +\def\bbbn{{\rm I!N}} %natuerliche Zahlen +\def\bbbf{{\rm I!F}} +\def\bbbh{{\rm I!H}} +\def\bbbk{{\rm I!K}} +\def\bbbp{{\rm I!P}} +\def\bbbone{{\mathchoice {\rm 1\mskip-4mu l} {\rm 1\mskip-4mu l} +{\rm 1\mskip-4.5mu l} {\rm 1\mskip-5mu l}}} +\def\bbbc{{\mathchoice {\setbox0=\hbox{$\displaystyle\rm C$}\hbox{\hbox +to0pt{\kern0.4\wd0\vrule height0.9\ht0\hss}\box0}} +{\setbox0=\hbox{$\textstyle\rm C$}\hbox{\hbox +to0pt{\kern0.4\wd0\vrule height0.9\ht0\hss}\box0}} +{\setbox0=\hbox{$\scriptstyle\rm C$}\hbox{\hbox +to0pt{\kern0.4\wd0\vrule height0.9\ht0\hss}\box0}} +{\setbox0=\hbox{$\scriptscriptstyle\rm C$}\hbox{\hbox +to0pt{\kern0.4\wd0\vrule height0.9\ht0\hss}\box0}}}} +\def\bbbq{{\mathchoice {\setbox0=\hbox{$\displaystyle\rm +Q$}\hbox{\raise +0.15\ht0\hbox to0pt{\kern0.4\wd0\vrule height0.8\ht0\hss}\box0}} +{\setbox0=\hbox{$\textstyle\rm Q$}\hbox{\raise +0.15\ht0\hbox to0pt{\kern0.4\wd0\vrule height0.8\ht0\hss}\box0}} +{\setbox0=\hbox{$\scriptstyle\rm Q$}\hbox{\raise +0.15\ht0\hbox to0pt{\kern0.4\wd0\vrule height0.7\ht0\hss}\box0}} +{\setbox0=\hbox{$\scriptscriptstyle\rm Q$}\hbox{\raise +0.15\ht0\hbox to0pt{\kern0.4\wd0\vrule height0.7\ht0\hss}\box0}}}} +\def\bbbt{{\mathchoice {\setbox0=\hbox{$\displaystyle\rm +T$}\hbox{\hbox to0pt{\kern0.3\wd0\vrule height0.9\ht0\hss}\box0}} +{\setbox0=\hbox{$\textstyle\rm T$}\hbox{\hbox +to0pt{\kern0.3\wd0\vrule height0.9\ht0\hss}\box0}} +{\setbox0=\hbox{$\scriptstyle\rm T$}\hbox{\hbox +to0pt{\kern0.3\wd0\vrule height0.9\ht0\hss}\box0}} +{\setbox0=\hbox{$\scriptscriptstyle\rm T$}\hbox{\hbox +to0pt{\kern0.3\wd0\vrule height0.9\ht0\hss}\box0}}}} +\def\bbbs{{\mathchoice +{\setbox0=\hbox{$\displaystyle \rm S$}\hbox{\raise0.5\ht0\hbox +to0pt{\kern0.35\wd0\vrule height0.45\ht0\hss}\hbox +to0pt{\kern0.55\wd0\vrule height0.5\ht0\hss}\box0}} +{\setbox0=\hbox{$\textstyle \rm S$}\hbox{\raise0.5\ht0\hbox +to0pt{\kern0.35\wd0\vrule height0.45\ht0\hss}\hbox +to0pt{\kern0.55\wd0\vrule height0.5\ht0\hss}\box0}} +{\setbox0=\hbox{$\scriptstyle \rm S$}\hbox{\raise0.5\ht0\hbox +to0pt{\kern0.35\wd0\vrule height0.45\ht0\hss}\raise0.05\ht0\hbox +to0pt{\kern0.5\wd0\vrule height0.45\ht0\hss}\box0}} +{\setbox0=\hbox{$\scriptscriptstyle\rm S$}\hbox{\raise0.5\ht0\hbox +to0pt{\kern0.4\wd0\vrule height0.45\ht0\hss}\raise0.05\ht0\hbox +to0pt{\kern0.55\wd0\vrule height0.45\ht0\hss}\box0}}}} +\def\bbbz{{\mathchoice {\hbox{$\mathsf\textstyle Z\kern-0.4em Z$}} +{\hbox{$\mathsf\textstyle Z\kern-0.4em Z$}} +{\hbox{$\mathsf\scriptstyle Z\kern-0.3em Z$}} +{\hbox{$\mathsf\scriptscriptstyle Z\kern-0.2em Z$}}}} + +\let\ts, + +\setlength\leftmargini {17\p@} +\setlength\leftmargin {\leftmargini} +\setlength\leftmarginii {\leftmargini} +\setlength\leftmarginiii {\leftmargini} +\setlength\leftmarginiv {\leftmargini} +\setlength \labelsep {.5em} +\setlength \labelwidth{\leftmargini} +\addtolength\labelwidth{-\labelsep} + +\def@listI{\leftmargin\leftmargini + \parsep 0\p@ @plus1\p@ @minus\p@ + \topsep 8\p@ @plus2\p@ @minus4\p@ + \itemsep0\p@} +\let@listi@listI +@listi +\def@listii {\leftmargin\leftmarginii + \labelwidth\leftmarginii + \advance\labelwidth-\labelsep + \topsep 0\p@ @plus2\p@ @minus\p@} +\def@listiii{\leftmargin\leftmarginiii + \labelwidth\leftmarginiii + \advance\labelwidth-\labelsep + \topsep 0\p@ @plus\p@@minus\p@ + \parsep \z@ + \partopsep \p@ @plus\z@ @minus\p@} + +\renewcommand\labelitemi{\normalfont\bfseries --} +\renewcommand\labelitemii{$\m@th\bullet$} + +\setlength\arraycolsep{1.4\p@} +\setlength\tabcolsep{1.4\p@} + +\def\tableofcontents{\chapter*{\contentsname@mkboth{{\contentsname}}% + {{\contentsname}}} + \def\authcount##1{\setcounter{auco}{##1}\setcounter{@auth}{1}} + \def\lastand{\ifnum\value{auco}=2\relax + \unskip{} \andname\ + \else + \unskip \lastandname\ + \fi}% + \def\and{\stepcounter{@auth}\relax + \ifnum\value{@auth}=\value{auco}% + \lastand + \else + \unskip, + \fi}% + @starttoc{toc}\if@restonecol\twocolumn\fi} + +\def\l@part#1#2{\addpenalty{@secpenalty}% + \addvspace{2em plus\p@}% % space above part line + \begingroup + \parindent \z@ + \rightskip \z@ plus 5em + \hrule\vskip5pt + \large % same size as for a contribution heading + \bfseries\boldmath % set line in boldface + \leavevmode % TeX command to enter horizontal mode. + #1\par + \vskip5pt + \hrule + \vskip1pt + \nobreak % Never break after part entry + \endgroup} + +\def@dotsep{2} + +\def\hyperhrefextend{\ifx\hyper@anchor@undefined\else +{chapter.\thechapter}\fi} + +\def\addnumcontentsmark#1#2#3{% +\addtocontents{#1}{\protect\contentsline{#2}{\protect\numberline + {\thechapter}#3}{\thepage}\hyperhrefextend}} +\def\addcontentsmark#1#2#3{% +\addtocontents{#1}{\protect\contentsline{#2}{#3}{\thepage}\hyperhrefextend}} +\def\addcontentsmarkwop#1#2#3{% +\addtocontents{#1}{\protect\contentsline{#2}{#3}{0}\hyperhrefextend}} + +\def@adcmk[#1]{\ifcase #1 \or +\def@gtempa{\addnumcontentsmark}% + \or \def@gtempa{\addcontentsmark}% + \or \def@gtempa{\addcontentsmarkwop}% + \fi@gtempa{toc}{chapter}} +\def\addtocmark{@ifnextchar[{@adcmk}{@adcmk[3]}} + +\def\l@chapter#1#2{\addpenalty{-@highpenalty} + \vskip 1.0em plus 1pt @tempdima 1.5em \begingroup + \parindent \z@ \rightskip @pnumwidth + \parfillskip -@pnumwidth + \leavevmode \advance\leftskip@tempdima \hskip -\leftskip + {\large\bfseries\boldmath#1}\ifx0#2\hfil\null + \else + \nobreak + \leaders\hbox{$\m@th \mkern @dotsep mu.\mkern + @dotsep mu$}\hfill + \nobreak\hbox to@pnumwidth{\hss #2}% + \fi\par + \penalty@highpenalty \endgroup} + +\def\l@title#1#2{\addpenalty{-@highpenalty} + \addvspace{8pt plus 1pt} + @tempdima \z@ + \begingroup + \parindent \z@ \rightskip @tocrmarg + \parfillskip -@tocrmarg + \leavevmode \advance\leftskip@tempdima \hskip -\leftskip + #1\nobreak + \leaders\hbox{$\m@th \mkern @dotsep mu.\mkern + @dotsep mu$}\hfill + \nobreak\hbox to@pnumwidth{\hss #2}\par + \penalty@highpenalty \endgroup} + +\setcounter{tocdepth}{0} +\newdimen\tocchpnum +\newdimen\tocsecnum +\newdimen\tocsectotal +\newdimen\tocsubsecnum +\newdimen\tocsubsectotal +\newdimen\tocsubsubsecnum +\newdimen\tocsubsubsectotal +\newdimen\tocparanum +\newdimen\tocparatotal +\newdimen\tocsubparanum +\tocchpnum=\z@ % no chapter numbers +\tocsecnum=15\p@ % section 88. plus 2.222pt +\tocsubsecnum=23\p@ % subsection 88.8 plus 2.222pt +\tocsubsubsecnum=27\p@ % subsubsection 88.8.8 plus 1.444pt +\tocparanum=35\p@ % paragraph 88.8.8.8 plus 1.666pt +\tocsubparanum=43\p@ % subparagraph 88.8.8.8.8 plus 1.888pt +\def\calctocindent{% +\tocsectotal=\tocchpnum +\advance\tocsectotal by\tocsecnum +\tocsubsectotal=\tocsectotal +\advance\tocsubsectotal by\tocsubsecnum +\tocsubsubsectotal=\tocsubsectotal +\advance\tocsubsubsectotal by\tocsubsubsecnum +\tocparatotal=\tocsubsubsectotal +\advance\tocparatotal by\tocparanum} +\calctocindent + +\def\l@section{@dottedtocline{1}{\tocchpnum}{\tocsecnum}} +\def\l@subsection{@dottedtocline{2}{\tocsectotal}{\tocsubsecnum}} +\def\l@subsubsection{@dottedtocline{3}{\tocsubsectotal}{\tocsubsubsecnum}} +\def\l@paragraph{@dottedtocline{4}{\tocsubsubsectotal}{\tocparanum}} +\def\l@subparagraph{@dottedtocline{5}{\tocparatotal}{\tocsubparanum}} + +\def\listoffigures{@restonecolfalse\if@twocolumn@restonecoltrue\onecolumn + \fi\section*{\listfigurename@mkboth{{\listfigurename}}{{\listfigurename}}} + @starttoc{lof}\if@restonecol\twocolumn\fi} +\def\l@figure{@dottedtocline{1}{0em}{1.5em}} + +\def\listoftables{@restonecolfalse\if@twocolumn@restonecoltrue\onecolumn + \fi\section*{\listtablename@mkboth{{\listtablename}}{{\listtablename}}} + @starttoc{lot}\if@restonecol\twocolumn\fi} +\let\l@table\l@figure + +\renewcommand\listoffigures{% + \section*{\listfigurename + @mkboth{\listfigurename}{\listfigurename}}% + @starttoc{lof}% + } + +\renewcommand\listoftables{% + \section*{\listtablename + @mkboth{\listtablename}{\listtablename}}% + @starttoc{lot}% + } + +\ifx\oribibl\undefined +\ifx\citeauthoryear\undefined +\renewenvironment{thebibliography}[1] + {\section*{\refname} + \def@biblabel##1{##1.} + \small + \list{@biblabel{@arabic\c@enumiv}}% + {\settowidth\labelwidth{@biblabel{#1}}% + \leftmargin\labelwidth + \advance\leftmargin\labelsep + \if@openbib + \advance\leftmargin\bibindent + \itemindent -\bibindent + \listparindent \itemindent + \parsep \z@ + \fi + \usecounter{enumiv}% + \let\p@enumiv@empty + \renewcommand\theenumiv{@arabic\c@enumiv}}% + \if@openbib + \renewcommand\newblock{\par}% + \else + \renewcommand\newblock{\hskip .11em @plus.33em @minus.07em}% + \fi + \sloppy\clubpenalty4000\widowpenalty4000% + \sfcode`.=@m} + {\def@noitemerr + {@latex@warning{Empty `thebibliography' environment}}% + \endlist} +\def@lbibitem[#1]#2{\item[{[#1]}\hfill]\if@filesw + {\let\protect\noexpand\immediate + \write@auxout{\string\bibcite{#2}{#1}}}\fi\ignorespaces} +\newcount@tempcntc +\def@citex[#1]#2{\if@filesw\immediate\write@auxout{\string\citation{#2}}\fi + @tempcnta\z@@tempcntb\m@ne\def@citea{}@cite{@for@citeb:=#2\do + {@ifundefined + {b@@citeb}{@citeo@tempcntb\m@ne@citea\def@citea{,}{\bfseries + ?}@warning + {Citation `@citeb' on page \thepage \space undefined}}% + {\setbox\z@\hbox{\global@tempcntc0\csname b@@citeb\endcsname\relax}% + \ifnum@tempcntc=\z@ @citeo@tempcntb\m@ne + @citea\def@citea{,}\hbox{\csname b@@citeb\endcsname}% + \else + \advance@tempcntb@ne + \ifnum@tempcntb=@tempcntc + \else\advance@tempcntb\m@ne@citeo + @tempcnta@tempcntc@tempcntb@tempcntc\fi\fi}}@citeo}{#1}} +\def@citeo{\ifnum@tempcnta>@tempcntb\else + @citea\def@citea{,,\hskip\z@skip}% + \ifnum@tempcnta=@tempcntb\the@tempcnta\else + {\advance@tempcnta@ne\ifnum@tempcnta=@tempcntb \else + \def@citea{--}\fi + \advance@tempcnta\m@ne\the@tempcnta@citea\the@tempcntb}\fi\fi} +\else +\renewenvironment{thebibliography}[1] + {\section*{\refname} + \small + \list{}% + {\settowidth\labelwidth{}% + \leftmargin\parindent + \itemindent=-\parindent + \labelsep=\z@ + \if@openbib + \advance\leftmargin\bibindent + \itemindent -\bibindent + \listparindent \itemindent + \parsep \z@ + \fi + \usecounter{enumiv}% + \let\p@enumiv@empty + \renewcommand\theenumiv{}}% + \if@openbib + \renewcommand\newblock{\par}% + \else + \renewcommand\newblock{\hskip .11em @plus.33em @minus.07em}% + \fi + \sloppy\clubpenalty4000\widowpenalty4000% + \sfcode`.=@m} + {\def@noitemerr + {@latex@warning{Empty `thebibliography' environment}}% + \endlist} + \def@cite#1{#1}% + \def@lbibitem[#1]#2{\item[]\if@filesw + {\def\protect##1{\string ##1\space}\immediate + \write@auxout{\string\bibcite{#2}{#1}}}\fi\ignorespaces} + \fi +\else +@cons@openbib@code{\noexpand\small} +\fi + +\def\idxquad{\hskip 10\p@}% space that divides entry from number + +\def@idxitem{\par\hangindent 10\p@} + +\def\subitem{\par\setbox0=\hbox{--\enspace}% second order + \noindent\hangindent\wd0\box0}% index entry + +\def\subsubitem{\par\setbox0=\hbox{--,--\enspace}% third + \noindent\hangindent\wd0\box0}% order index entry + +\def\indexspace{\par \vskip 10\p@ plus5\p@ minus3\p@\relax} + +\renewenvironment{theindex} + {@mkboth{\indexname}{\indexname}% + \thispagestyle{empty}\parindent\z@ + \parskip\z@ @plus .3\p@\relax + \let\item\par + \def,{\relax\ifmmode\mskip\thinmuskip + \else\hskip0.2em\ignorespaces\fi}% + \normalfont\small + \begin{multicols}{2}[@makeschapterhead{\indexname}]% + } + {\end{multicols}} + +\renewcommand\footnoterule{% + \kern-3\p@ + \hrule@width 2truecm + \kern2.6\p@} + \newdimen\fnindent + \fnindent1em +\long\def@makefntext#1{% + \parindent \fnindent% + \leftskip \fnindent% + \noindent + \llap{\hb@xt@1em{\hss@makefnmark\ }}\ignorespaces#1} + +\long\def@makecaption#1#2{% + \vskip\abovecaptionskip + \sbox@tempboxa{{\bfseries #1.} #2}% + \ifdim \wd@tempboxa >\hsize + {\bfseries #1.} #2\par + \else + \global @minipagefalse + \hb@xt@\hsize{\hfil\box@tempboxa\hfil}% + \fi + \vskip\belowcaptionskip} + +\def\fps@figure{htbp} +\def\fnum@figure{\figurename\thinspace\thefigure} +\def @floatboxreset {% + \reset@font + \small + @setnobreak + @setminipage +} +\def\fps@table{htbp} +\def\fnum@table{\tablename~\thetable} +\renewenvironment{table} + {\setlength\abovecaptionskip{0\p@}% + \setlength\belowcaptionskip{10\p@}% + @float{table}} + {\end@float} +\renewenvironment{table*} + {\setlength\abovecaptionskip{0\p@}% + \setlength\belowcaptionskip{10\p@}% + @dblfloat{table}} + {\end@dblfloat} + +\long\def@caption#1[#2]#3{\par\addcontentsline{\csname + ext@#1\endcsname}{#1}{\protect\numberline{\csname + the#1\endcsname}{\ignorespaces #2}}\begingroup + @parboxrestore + @makecaption{\csname fnum@#1\endcsname}{\ignorespaces #3}\par + \endgroup} + +% LaTeX does not provide a command to enter the authors institute +% addresses. The \institute command is defined here. + +\newcounter{@inst} +\newcounter{@auth} +\newcounter{auco} +\def\andname{and} +\def\lastandname{\unskip, and} +\newdimen\instindent +\newbox\authrun +\newtoks\authorrunning +\newtoks\tocauthor +\newbox\titrun +\newtoks\titlerunning +\newtoks\toctitle + +\def\clearheadinfo{\gdef@author{No Author Given}% + \gdef@title{No Title Given}% + \gdef@subtitle{}% + \gdef@institute{No Institute Given}% + \gdef@thanks{}% + \global\titlerunning={}\global\authorrunning={}% + \global\toctitle={}\global\tocauthor={}} + +\def\institute#1{\gdef@institute{#1}} + +\def\institutename{\par + \begingroup + \parskip=\z@ + \parindent=\z@ + \setcounter{@inst}{1}% + \def\and{\par\stepcounter{@inst}% + \noindent$^{\the@inst}$\enspace\ignorespaces}% + \setbox0=\vbox{\def\thanks##1{}@institute}% + \ifnum\c@@inst=1\relax + \else + \setcounter{footnote}{\c@@inst}% + \setcounter{@inst}{1}% + \noindent$^{\the@inst}$\enspace + \fi + \ignorespaces + @institute\par + \endgroup} + +\def@fnsymbol#1{\ensuremath{\ifcase#1\or\star\or{\star\star}\or + {\star\star\star}\or \dagger\or \ddagger\or + \mathchar "278\or \mathchar "27B\or |\or **\or \dagger\dagger + \or \ddagger\ddagger \else@ctrerr\fi}} + +\def\inst#1{\unskip$^{#1}$} +\def\fnmsep{\unskip$^,$} +\def\email#1{{\tt#1}} +\AtBeginDocument{@ifundefined{url}{\def\url#1{#1}}{}} +\def\homedir{~{ }} + +\def\subtitle#1{\gdef@subtitle{#1}} +\clearheadinfo + +\renewcommand\maketitle{\newpage + \refstepcounter{chapter}% + \stepcounter{section}% + \setcounter{section}{0}% + \setcounter{subsection}{0}% + \setcounter{figure}{0} + \setcounter{table}{0} + \setcounter{equation}{0} + \setcounter{footnote}{0}% + \begingroup + \parindent=\z@ + \renewcommand\thefootnote{@fnsymbol\c@footnote}% + \if@twocolumn + \ifnum \col@number=@ne + @maketitle + \else + \twocolumn[@maketitle]% + \fi + \else + \newpage + \global@topnum\z@ % Prevents figures from going at top of page. + @maketitle + \fi + \thispagestyle{empty}@thanks +% + \def\{\unskip\ \ignorespaces}\def\inst##1{\unskip{}}% + \def\thanks##1{\unskip{}}\def\fnmsep{\unskip}% + \instindent=\hsize + \advance\instindent by-\headlineindent + \if!\the\toctitle!\addcontentsline{toc}{title}{@title}\else + \addcontentsline{toc}{title}{\the\toctitle}\fi + \if@runhead + \if!\the\titlerunning!\else + \edef@title{\the\titlerunning}% + \fi + \global\setbox\titrun=\hbox{\small\rm\unboldmath\ignorespaces@title}% + \ifdim\wd\titrun>\instindent + \typeout{Title too long for running head. Please supply}% + \typeout{a shorter form with \string\titlerunning\space prior to + \string\maketitle}% + \global\setbox\titrun=\hbox{\small\rm + Title Suppressed Due to Excessive Length}% + \fi + \xdef@title{\copy\titrun}% + \fi +% + \if!\the\tocauthor!\relax + {\def\and{\noexpand\protect\noexpand\and}% + \protected@xdef\toc@uthor{@author}}% + \else + \def\{\noexpand\protect\noexpand\newline}% + \protected@xdef\scratch{\the\tocauthor}% + \protected@xdef\toc@uthor{\scratch}% + \fi + \addtocontents{toc}{{\protect\raggedright\protect\leftskip15\p@ + \protect\rightskip@tocrmarg + \protect\itshape\toc@uthor\protect\endgraf}}% + \if@runhead + \if!\the\authorrunning! + \value{@inst}=\value{@auth}% + \setcounter{@auth}{1}% + \else + \edef@author{\the\authorrunning}% + \fi + \global\setbox\authrun=\hbox{\small\unboldmath@author\unskip}% + \ifdim\wd\authrun>\instindent + \typeout{Names of authors too long for running head. Please supply}% + \typeout{a shorter form with \string\authorrunning\space prior to + \string\maketitle}% + \global\setbox\authrun=\hbox{\small\rm + Authors Suppressed Due to Excessive Length}% + \fi + \xdef@author{\copy\authrun}% + \markboth{@author}{@title}% + \fi + \endgroup + \setcounter{footnote}{0}% + \clearheadinfo} +% +\def@maketitle{\newpage + \markboth{}{}% + \def\lastand{\ifnum\value{@inst}=2\relax + \unskip{} \andname\ + \else + \unskip \lastandname\ + \fi}% + \def\and{\stepcounter{@auth}\relax + \ifnum\value{@auth}=\value{@inst}% + \lastand + \else + \unskip, + \fi}% + \begin{center}% + {\Large \bfseries\boldmath + \pretolerance=10000 + @title \par}\vskip .8cm +\if!@subtitle!\else {\large \bfseries\boldmath + \vskip -.65cm + \pretolerance=10000 + @subtitle \par}\vskip .8cm\fi + \setbox0=\vbox{\setcounter{@auth}{1}\def\and{\stepcounter{@auth}}% + \def\thanks##1{}@author}% + \global\value{@inst}=\value{@auth}% + \global\value{auco}=\value{@auth}% + \setcounter{@auth}{1}% +{\lineskip .5em +\noindent\ignorespaces +@author\vskip.35cm} + {\small\institutename} + \end{center}% + } + +% definition of the "\spnewtheorem" command. +% +% Usage: +% +% \spnewtheorem{env_nam}{caption}[within]{cap_font}{body_font} +% or \spnewtheorem{env_nam}[numbered_like]{caption}{cap_font}{body_font} +% or \spnewtheorem*{env_nam}{caption}{cap_font}{body_font} +% +% New is "cap_font" and "body_font". It stands for +% fontdefinition of the caption and the text itself. +% +% "\spnewtheorem*" gives a theorem without number. +% +% A defined spnewthoerem environment is used as described +% by Lamport. +% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +\def@thmcountersep{} +\def@thmcounterend{.} + +\def\spnewtheorem{@ifstar{@sthm}{@Sthm}} + +% definition of \spnewtheorem with number + +\def@spnthm#1#2{% + @ifnextchar[{@spxnthm{#1}{#2}}{@spynthm{#1}{#2}}} +\def@Sthm#1{@ifnextchar[{@spothm{#1}}{@spnthm{#1}}} + +\def@spxnthm#1#2[#3]#4#5{\expandafter@ifdefinable\csname #1\endcsname + {@definecounter{#1}@addtoreset{#1}{#3}% + \expandafter\xdef\csname the#1\endcsname{\expandafter\noexpand + \csname the#3\endcsname \noexpand@thmcountersep @thmcounter{#1}}% + \expandafter\xdef\csname #1name\endcsname{#2}% + \global@namedef{#1}{@spthm{#1}{\csname #1name\endcsname}{#4}{#5}}% + \global@namedef{end#1}{@endtheorem}}} + +\def@spynthm#1#2#3#4{\expandafter@ifdefinable\csname #1\endcsname + {@definecounter{#1}% + \expandafter\xdef\csname the#1\endcsname{@thmcounter{#1}}% + \expandafter\xdef\csname #1name\endcsname{#2}% + \global@namedef{#1}{@spthm{#1}{\csname #1name\endcsname}{#3}{#4}}% + \global@namedef{end#1}{@endtheorem}}} + +\def@spothm#1[#2]#3#4#5{% + @ifundefined{c@#2}{@latexerr{No theorem environment `#2' defined}@eha}% + {\expandafter@ifdefinable\csname #1\endcsname + {\global@namedef{the#1}{@nameuse{the#2}}% + \expandafter\xdef\csname #1name\endcsname{#3}% + \global@namedef{#1}{@spthm{#2}{\csname #1name\endcsname}{#4}{#5}}% + \global@namedef{end#1}{@endtheorem}}}} + +\def@spthm#1#2#3#4{\topsep 7\p@ @plus2\p@ @minus4\p@ +\refstepcounter{#1}% +@ifnextchar[{@spythm{#1}{#2}{#3}{#4}}{@spxthm{#1}{#2}{#3}{#4}}} + +\def@spxthm#1#2#3#4{@spbegintheorem{#2}{\csname the#1\endcsname}{#3}{#4}% + \ignorespaces} + +\def@spythm#1#2#3#4[#5]{@spopargbegintheorem{#2}{\csname + the#1\endcsname}{#5}{#3}{#4}\ignorespaces} + +\def@spbegintheorem#1#2#3#4{\trivlist + \item[\hskip\labelsep{#3#1\ #2@thmcounterend}]#4} + +\def@spopargbegintheorem#1#2#3#4#5{\trivlist + \item[\hskip\labelsep{#4#1\ #2}]{#4(#3)@thmcounterend\ }#5} + +% definition of \spnewtheorem* without number + +\def@sthm#1#2{@Ynthm{#1}{#2}} + +\def@Ynthm#1#2#3#4{\expandafter@ifdefinable\csname #1\endcsname + {\global@namedef{#1}{@Thm{\csname #1name\endcsname}{#3}{#4}}% + \expandafter\xdef\csname #1name\endcsname{#2}% + \global@namedef{end#1}{@endtheorem}}} + +\def@Thm#1#2#3{\topsep 7\p@ @plus2\p@ @minus4\p@ +@ifnextchar[{@Ythm{#1}{#2}{#3}}{@Xthm{#1}{#2}{#3}}} + +\def@Xthm#1#2#3{@Begintheorem{#1}{#2}{#3}\ignorespaces} + +\def@Ythm#1#2#3[#4]{@Opargbegintheorem{#1} + {#4}{#2}{#3}\ignorespaces} + +\def@Begintheorem#1#2#3{#3\trivlist + \item[\hskip\labelsep{#2#1@thmcounterend}]} + +\def@Opargbegintheorem#1#2#3#4{#4\trivlist + \item[\hskip\labelsep{#3#1}]{#3(#2)@thmcounterend\ }} + +\if@envcntsect + \def@thmcountersep{.} + \spnewtheorem{theorem}{Theorem}[section]{\bfseries}{\itshape} +\else + \spnewtheorem{theorem}{Theorem}{\bfseries}{\itshape} + \if@envcntreset + @addtoreset{theorem}{section} + \else + @addtoreset{theorem}{chapter} + \fi +\fi + +%definition of divers theorem environments +\spnewtheorem*{claim}{Claim}{\itshape}{\rmfamily} +\spnewtheorem*{proof}{Proof}{\itshape}{\rmfamily} +\if@envcntsame % alle Umgebungen wie Theorem. + \def\spn@wtheorem#1#2#3#4{@spothm{#1}[theorem]{#2}{#3}{#4}} +\else % alle Umgebungen mit eigenem Zaehler + \if@envcntsect % mit section numeriert + \def\spn@wtheorem#1#2#3#4{@spxnthm{#1}{#2}[section]{#3}{#4}} + \else % nicht mit section numeriert + \if@envcntreset + \def\spn@wtheorem#1#2#3#4{@spynthm{#1}{#2}{#3}{#4} + @addtoreset{#1}{section}} + \else + \def\spn@wtheorem#1#2#3#4{@spynthm{#1}{#2}{#3}{#4} + @addtoreset{#1}{chapter}}% + \fi + \fi +\fi +\spn@wtheorem{case}{Case}{\itshape}{\rmfamily} +\spn@wtheorem{conjecture}{Conjecture}{\itshape}{\rmfamily} +\spn@wtheorem{corollary}{Corollary}{\bfseries}{\itshape} +\spn@wtheorem{definition}{Definition}{\bfseries}{\itshape} +\spn@wtheorem{example}{Example}{\itshape}{\rmfamily} +\spn@wtheorem{exercise}{Exercise}{\itshape}{\rmfamily} +\spn@wtheorem{lemma}{Lemma}{\bfseries}{\itshape} +\spn@wtheorem{note}{Note}{\itshape}{\rmfamily} +\spn@wtheorem{problem}{Problem}{\itshape}{\rmfamily} +\spn@wtheorem{property}{Property}{\itshape}{\rmfamily} +\spn@wtheorem{proposition}{Proposition}{\bfseries}{\itshape} +\spn@wtheorem{question}{Question}{\itshape}{\rmfamily} +\spn@wtheorem{solution}{Solution}{\itshape}{\rmfamily} +\spn@wtheorem{remark}{Remark}{\itshape}{\rmfamily} + +\def@takefromreset#1#2{% + \def@tempa{#1}% + \let@tempd@elt + \def@elt##1{% + \def@tempb{##1}% + \ifx@tempa@tempb\else + @addtoreset{##1}{#2}% + \fi}% + \expandafter\expandafter\let\expandafter@tempc\csname cl@#2\endcsname + \expandafter\def\csname cl@#2\endcsname{}% + @tempc + \let@elt@tempd} + +\def\theopargself{\def@spopargbegintheorem##1##2##3##4##5{\trivlist + \item[\hskip\labelsep{##4##1\ ##2}]{##4##3@thmcounterend\ }##5} + \def@Opargbegintheorem##1##2##3##4{##4\trivlist + \item[\hskip\labelsep{##3##1}]{##3##2@thmcounterend\ }} + } + +\renewenvironment{abstract}{% + \list{}{\advance\topsep by0.35cm\relax\small + \leftmargin=1cm + \labelwidth=\z@ + \listparindent=\z@ + \itemindent\listparindent + \rightmargin\leftmargin}\item[\hskip\labelsep + \bfseries\abstractname]} + {\endlist} +\renewcommand{\abstractname}{Abstract.} +\renewcommand{\contentsname}{Table of Contents} +\renewcommand{\figurename}{Fig.} +\renewcommand{\tablename}{Table} + +\newdimen\headlineindent % dimension for space between +\headlineindent=1.166cm % number and text of headings. + +\def\ps@headings{\let@mkboth@gobbletwo + \let@oddfoot@empty\let@evenfoot@empty + \def@evenhead{\normalfont\small\rlap{\thepage}\hspace{\headlineindent}% + \leftmark\hfil} + \def@oddhead{\normalfont\small\hfil\rightmark\hspace{\headlineindent}% + \llap{\thepage}} + \def\chaptermark##1{}% + \def\sectionmark##1{}% + \def\subsectionmark##1{}} + +\def\ps@titlepage{\let@mkboth@gobbletwo + \let@oddfoot@empty\let@evenfoot@empty + \def@evenhead{\normalfont\small\rlap{\thepage}\hspace{\headlineindent}% + \hfil} + \def@oddhead{\normalfont\small\hfil\hspace{\headlineindent}% + \llap{\thepage}} + \def\chaptermark##1{}% + \def\sectionmark##1{}% + \def\subsectionmark##1{}} + +\if@runhead\ps@headings\else +\ps@empty\fi + +\setlength\arraycolsep{1.4\p@} +\setlength\tabcolsep{1.4\p@} + +\endinput + diff --git a/2009/torflow/torflow.bib b/2009/torflow/torflow.bib new file mode 100644 index 0000000..c8c667e --- /dev/null +++ b/2009/torflow/torflow.bib @@ -0,0 +1,150 @@ + +@inproceedings{tor-design, + title = {{Tor}: The Second-Generation Onion Router}, + author = {Roger Dingledine and Nick Mathewson and Paul Syverson}, + booktitle = {Proceedings of the 13th USENIX Security Symposium}, + year = {2004}, + month = {August}, +} + +@Misc{path-spec, + author = {Roger Dingledine and Nick Mathewson}, + title = {{Tor Path Specifications}}, + note = {\url{https://git.torproject.org/checkout/tor/master/doc/spec/path-spec.txt%7D%7D, +} + +@Misc{nickm-iocp, + key = {nickm-iocp}, + title = {{Some Notes on Progress with IOCP and Libevent}}, + author = {Nick Mathewson}, + note = {\url{https://blog.torproject.org/blog/some-notes-progress-iocp-and-libevent%7D%7D +} + +@Misc{murdoch-economics, + key = {murdoch-economics}, + title = {{Economics of Tor performance}}, + author = {Steven J. Murdoch}, + note = {\url{http://www.lightbluetouchpaper.org/2007/07/18/economics-of-tor-performance/%... +} + +@Misc{perry-bh07, + key = {perry-bh07}, + title = {{Securing the Tor Network}}, + author = {Mike Perry}, + note = {\url{http://www.blackhat.com/presentations/bh-usa-07/Perry/Presentation/bh-usa-07... +} + +@Misc{perry-ssh-ortalk, + key = {perry-ssh-ortalk}, + title = {{SSH Key Spoofing}}, + author = {Mike Perry}, + note = {\url{http://archives.seul.org/or/talk/Jan-2007/msg00030.html%7D%7D +} + +@Misc{control-spec, + author = {Roger Dingledine and Nick Mathewson}, + title = {Tor Control Protocol Specifications}, + note = {\url{https://git.torproject.org/checkout/tor/master/doc/spec/control-spec.txt%7D%..., +} + +@Misc{dir-spec, + author = {Roger Dingledine and Nick Mathewson}, + title = {Tor Control Protocol Specifications}, + note = {\url{https://git.torproject.org/checkout/tor/master/doc/spec/dir-spec.txt%7D%7D, +} + +@Misc{Elixir, + key = {Elixir}, + title = {{Elixir}}, + note = {\url{http://elixir.ematia.de/trac/wiki%7D%7D +} + +@Misc{SQLAlchemy, + key = {SQLALchemy}, + title = {{SQLAlchemy Database Toolkit for Python}}, + note = {\url{http://www.sqlalchemy.org/%7D%7D +} + +@Misc{BeautifulSoup, + key = {BeautifulSoup}, + title = {{Beautiful Soup: Elixir and Tonic}}, + note = {\url{http://www.crummy.com/software/BeautifulSoup/%7D%7D +} + +@Misc{Javascript.g, + key = {Javascript.g}, + title = {{Antlr Javascript Grammar}}, + note = {\url{http://www.antlr.org/grammar/1206736738015/JavaScript.g%7D%7D +} + +@mastersthesis{renner-thesis, + title = {{Performance-Improved Onion Routing}}, + author = {Johannes Renner}, + school = {Aachen Univiversity}, + year = {2007}, + month = {September}, +} + +@Misc{tor-spec, + author = {Roger Dingledine and Nick Mathewson}, + title = {{Tor Protocol Specifications}}, + note = {\url{https://git.torproject.org/checkout/tor/master/doc/spec/tor-spec.txt%7D%7D, +} + +@Misc{bug440, + author = {Mike Perry}, + title = {{Guard Nodes Not Weighted By Bandwidth}}, + note = {\url{http://bugs.torproject.org/flyspray/index.php?do=details%5C&id=440%7D%7D +} + +@Misc{perry-balancing, + author = {Mike Perry}, + title = {{Exit Balancing Patch}}, + note = {\url{http://archives.seul.org/or/dev/Jul-2007/msg00021.html%7D%7D +} + +@Misc{ads-malware, + author = {Betsy Schiffman}, + title = {{Hackers Use Banner Ads on Major Sites}}, + howpublished = {Wired Magazine}, + month = {Nov}, + year = {2007}, + note = {\url{http://www.wired.com/techbiz/media/news/2007/11/doubleclick%7D%7D, +} + +@Misc{fu-bh09, + key = {fu-bh09}, + title = {{One Cell is Enough to Break Tor's Anonymity}}, + author = {Xinwen Fu and Zhen Ling}, + note = {\url{http://www.blackhat.com/presentations/bh-dc-09/Fu/BlackHat-DC-09-Fu-Break-To... +} + +@inproceedings{tabriz-denial, + author = {Borisov,, Nikita and Danezis,, George and Mittal,, Prateek and Tabriz,, Parisa}, + title = {Denial of service or denial of security?}, + booktitle = {CCS '07: Proceedings of the 14th ACM conference on Computer and communications security}, + year = {2007}, + isbn = {978-1-59593-703-2}, + pages = {92--102}, + location = {Alexandria, Virginia, USA}, + doi = {http://doi.acm.org/10.1145/1315245.1315258%7D, + publisher = {ACM}, + address = {New York, NY, USA}, +} + +@inproceedings{mccoy-low, + author = {Bauer,, Kevin and McCoy,, Damon and Grunwald,, Dirk and Kohno,, +Tadayoshi and Sicker,, Douglas}, + title = {{Low-resource routing attacks against Tor}}, + booktitle = {WPES '07: Proceedings of the 2007 ACM workshop on Privacy in +electronic society}, + year = {2007}, + isbn = {978-1-59593-883-1}, + pages = {11--20}, + location = {Alexandria, Virginia, USA}, + doi = {http://doi.acm.org/10.1145/1314333.1314336%7D, + publisher = {ACM}, + address = {New York, NY, USA}, +} + + diff --git a/2009/torflow/torflow.tex b/2009/torflow/torflow.tex new file mode 100644 index 0000000..1abaebd --- /dev/null +++ b/2009/torflow/torflow.tex @@ -0,0 +1,713 @@ +% XXX: Change to llncs 11pt aka +%\documentclass{llncs} +\documentclass[letterpaper,11pt]{llncs} +%\documentclass{article} % llncs + +\usepackage{usenix} +\usepackage{url} +\usepackage{graphics} +\usepackage{amsmath} +\usepackage{listings} + +\setlength{\textwidth}{5.9in} +\setlength{\textheight}{8.4in} +\setlength{\topmargin}{.5cm} +\setlength{\oddsidemargin}{1cm} +\setlength{\evensidemargin}{1cm} + +\newenvironment{tightlist}{\begin{list}{$\bullet$}{ + \setlength{\itemsep}{0mm} + \setlength{\parsep}{0mm} + % \setlength{\labelsep}{0mm} + % \setlength{\labelwidth}{0mm} + % \setlength{\topsep}{0mm} + }}{\end{list}} + +\begin{document} + +\title{TorFlow: Tor Network Analysis} + +\author{Mike Perry \ The Internet \ mikeperry@fscked.org} + +%\institute{The Internet} + +\maketitle +\pagestyle{plain} + +\begin{abstract} + The Tor Network is a low-latency anonymity, privacy, and censorship + resistance network whose servers are run by volunteers around the + Internet. This distribution of trust creates resilience in the face + of compromise and censorship; but it also creates performance, + security, and usability issues. The TorFlow suite attempts to address + this by providing a library and associated tools for measuring Tor nodes + for reliability, capacity and integrity, with the ultimate goal of feeding + these measurements back into the Tor directory authorities. +\end{abstract} + +\section{Introduction} + +The Tor~\cite{tor-design} Network is a TCP overlay network whose +infrastructure is run entirely by volunteers. It is the largest public +anonymity network in the world, consisting of approximately 1500 nodes with a +total capacity of approximately 3Gbps, and almost 1Gbps of total exit +throughput. In over 6 years of operation, it has never gone down, and has +never had a ``flag day''. + +Clients that use the Tor network construct paths called circuits that consist +of 3 nodes (guard, middle, and exit) upon which they route multiple TCP +streams. The nodes in each circuit are chosen probabilistically according to +the maximum bandwidth they claim to observe themselves transmit over a 24 hour +period~\cite{dir-spec}. The Tor client software ensures that no two nodes run +by the same (cooperating) operator nor any two nodes from the same /16 netmask +are ever chosen in the same circuit~\cite{path-spec}. + +However, the same distributed and heterogeneous nature of the network that +gives Tor its strength is also a source of security, performance, and +usability issues. The largest barrier to widespread use of the network is +performance~\cite{murdoch-economics}, and the biggest user-visible performance +issue is not actually total capacity, but the high variance in circuit +performance and non-uniform distribution of network load.~\cite{perry-bh07} + +Moreover, there are a non-trivial number of nodes that alter content due to +misconfiguration, or much less often, due to malice. This most frequently +comes in the form of truncating TCP streams or failing DNS, but occasionally +presents itself as SSL spoofing or interception by the upstream ISP. On rare +occasion, SSH hijacking and web content injection have also been +observed.~\cite{perry-ssh-ortalk}. +% XXX: There's another ref for this involving web injection + +\section{Overview} + +The TorFlow suite attempts to address these issues with 4 major components. At +the core is the TorCtl control port and path selection library, which provides +the ability to create paths subject to arbitrary restrictions, measure various +aspects of node reliability and performance, and store results in-memory or +in a SQL database of your choice. + +In addition, three network scanners are built on top of this library: +SpeedRacer, BuildTimes, and SoaT (Snakes on a Tor). SpeedRacer measures +average stream capacity. BuildTimes measures circuit construction speeds and +failure rates. SoaT is a multi-protocol Tor exit node scanner, for detecting +misconfigured or malicious exit nodes. + +\section{Path Selection and Measurement Library} + +The Python-based TorCtl library was initially authored by Nick +Mathewson to provide programmatic access to the Tor Control Port +protocol~\cite{control-spec}. It has since been extended to provide the +ability to use modular components to build up custom path selection algorithms +and gather statistics on their characteristics. + +\subsection{Tor Control Port Protocol} + +The Tor Control Port protocol used by TorCtl is a plaintext TCP-based protocol +that provides well-formed information on Tor client status and events and +optionally enables control over circuit construction and association of SOCKS +streams to individual circuits. + +\begin{figure}[htp] +\centering +\includegraphics{ControlPort2.pdf} +\caption{Example Tor Control Port connection with representative Tor Traffic.} +\label{fig:ControlPort2.pdf} +\end{figure} + +\subsection{TorCtl Organization} + +\begin{figure}[htp] +\centering +\includegraphics{PathSupport.pdf} +\caption{TorCtl Core Class Diagram} +\label{fig:PathSupport.pdf} +\end{figure} + +TorCtl provides access to the Tor Control Port at several different layers of +abstraction. At the lowest layer is the TorCtl Connection object (not shown), +which is used to send commands to the control port and get responses. TorCtl +Connections are often associated with a TorCtl EventHandler instance, which is +passed objects representing parsed Tor Events. + +The EventHandler interface can be implemented directly, but is also extended +by the library to provide a ConsensusTracker, which maintains a Python-based +representation of the current Tor directory consensus as seen by the Tor +client. + +If a higher level of control over pathing is desired, programmers can choose +to utilize the Path Support routines by using a PathBuilder instance. The +PathBuilder is an EventHandler that tracks incoming stream events and builds +circuits for them according to the direction of a SelectionManager, which is +queried whenever a new path is needed. + +The provided SelectionManager breaks this construction down into +NodeGenerators managed by a PathSelector. NodeGenerators govern the +underlying probability distribution from which nodes are drawn. Uniform, +ordered, and Tor-compatible bandwidth-weighted node generators are provided. +One NodeGenerator instance exists for each hop in a path of length 2 up to +arbitrary N. + +Each NodeGenerator has a collection of zero to arbitrary N NodeRestrictions +that are used to restrict which nodes are eligible for generation. +Restrictions based on node exit policy, directory flags, identity key, +country, bandwidth, operating system, Tor version, and percentile rank are +provided. Meta-restrictions such as And, Or, Not, and N of M are also +provided. + +After a candidate path is generated using the NodeGenerators, the PathSelector +checks this path for validity against any supplied PathRestrictions. These +include Tor's Subnet16, NodeFamily, and UniqueNode restrictions. Additionally, +single continent, single country, continent changing, country changing, unique +country, and unique continent restrictions were contributed by Johannes Renner +for his research into geolocational path selection~\cite{renner-thesis}. + +\subsection{EventListener Statistics Support} + +The TorCtl library provides two main mechanisms for gathering statistics. +These are both implemented as EventListeners which can be attached to +arbitrary EventHandlers regardless of what is managing path construction +and stream servicing. + +The first is a hand-coded StatsHandler that computes a series of statistics on +circuit creation time and failure reason, and stream capacity and failure +reason. + +The second is a SQL-based system that stores circuit and/or stream events in +SQL tables. The SQL system uses Elixir~\cite{Elixir} and +SQLAlchemy~\cite{SQLAlchemy}, so the backend database can be any that is +supported by SQLAlchemy (which includes just about every modern database +backend). + +\section{Performance Measurements} + +TorFlow currently utilizes the TorCtl support library towards two main classes +of performance measurement: circuit-based and stream-based. The circuit-based +measurements are concerned with construction time and reliability. The +stream-based measurements are concerned primarily with stream capacity. + +\subsection{Circuit Construction Speed and Reliability} + +As stated previously, one of the major issues with Tor is the high variance of +performance of nodes and paths. One way to avoid overloaded paths is to simply +give up on circuits that take too long to build. The problem is that how long +to wait before giving up is heavily dependent on the local link, as it must be +traversed three times for each circuit construction due to the telescope-style +circuit construction Tor employs.~\cite{tor-spec}. + +With this in mind, we created a Google Summer of Code project to determine a +probability distribution that could be used to model Tor circuit construction +times and then to implement code in the Tor client itself to estimate a +particular client's distribution parameters and determine a proper circuit +timeout cutoff for that client that would cut out the slowest X% of paths +from usage. + +Fallon Chen took this project, and started out by creating a utility called +BuildTimes using TorCtl. It builds up to N circuits in parallel, subject to +configurable TorCtl NodeRestrictions. In addition to collecting TorCtl +aggregate statistics, it also logs circuit extend times to plaintext files +that can be easily post-processed. + +Based on her measurements, we were able to determine that the circuit build +times can be loosely modeled as a Pareto distribution, as shown in Figure +\ref{fig:buildtimes} below. They can also be more tightly modeled with a +Fr'{e}chet distribution, but the estimators for this distribution are not as +straightforward as Pareto, and for our purposes the only significant portion +of the distribution is the tail, which matches well enough. + +Moreover, the major irregularity occurring at 6000ms (and also to a lesser +degree at every second) in the histogram has been identified by Karsten +Loesing as being a result of our rate limiting algorithm emptying its token +buckets in sync across the network at the top of each second as opposed to +continuously. When this is addressed, the Pareto fit should improve. + +\begin{figure}[htp] +\centering +\includegraphics{0-93-100000-buildtimes-res100.pdf} +\caption{Network-wide bandwidth-weighted circuit build time distribution (ms).} +\label{fig:buildtimes} +\end{figure} + +Unfortunately, Fallon's research obligations over the summer prevented her +from completing the second half of the project and we have not yet +recalibrated Tor's circuit timeout in the client. + +\subsection{Guard Node Rebalancing} + +\begin{figure}[htp] +\centering +\includegraphics{ExtendsBar.pdf} +\includegraphics{ExtendsBar2.pdf} +\caption{Circuit construction times before and after guard rebalancing.} +\label{fig:Extends} +\end{figure} + +In 2007, an early TorFlow implementation was used to measure circuit +responsiveness and reliability of 5% slices of the network (lower percentiles +indicate higher advertised bandwidth). Repeated measurement showed that nodes +became progressively less responsive and more failure prone as they got +slower, up until the 50% mark, at which point the pattern suddenly stopped. +This pattern can be seen in the left side of Figures \ref{fig:Extends} and +\ref{fig:Failure}. + +This 50% mark was the same point where nodes ceased to be considered for +'guard' status. + +We eventually discovered that client guard node selection, instead of being +weighted based on bandwidth, was actually uniform. We developed a new algorithm +to fix this, as well as to properly account for weighting both guards and +exits according to their scarcity when being selected for other positions in +the network~\cite{bug440,perry-balancing}. + +Without an autoupdater, it took over a year for enough clients to upgrade for +the results to be visible in our scans, but it appears that at least among +guards, the load is now considerably more uniform. + +\begin{figure}[htp] +\centering +\includegraphics{CircFailure.pdf} +\includegraphics{CircFailure2.pdf} +\caption{Circuit Failure Rates before and after guard rebalancing} +\label{fig:Failure} +\end{figure} + +However, it is obvious that irregularities still remain. Interestingly, the +points of very low failure rates in Figure \ref{fig:Failure} correspond to the +periods between 01:00 and 03:00 PST, when most of the US is asleep, and +consistently appeared at that time in numerous scans. This seems to suggest we +should avoid capacity scans during those hours. It also suggests that circuit +reliability may be dependent on load in a non-linear fashion. One potential +source for this is CPU load: when Tor detects that is not able to complete +crypto operations fast enough, it begins dropping circuit creation cells. This +could explain the sharp difference in high load vs low load conditions for +circuit failure, but not for stream capacity. + +Furthermore, it appears in the right side of Figure \ref{fig:Failure} as +though the slower 50% of the network is now exhibiting significantly higher +failure percentages than the first 50%. In order to explore this, we ran a +number of additional circuit failure scans utilizing TorFlow's Node +Restriction capabilities. + +\subsection{Drilling Down with Restrictions} + +Our first guess was that middle nodes were bearing more than their proportion +of directory requests due to changes in client node selection in the guard +rebalancing fixes mentioned above. + +However, circuit construction scans showed this not to be the case. In fact, +it showed the exact opposite. Nodes with their directory port open did not +exhibit consistent increase in either circuit failure or extend time over +nodes without their directory port open, and middle nodes exhibited much less +circuit failure than guard and exit nodes. + +After more investigation and many scans, two consistent failure classes +emerged: Windows nodes, and non-bandwidth limited nodes, each of which seemed +to perform a bit worse as Guard and Exit nodes than as the middle nodes. + +\begin{figure}[htp] +\centering +\includegraphics{CircFailure-Win2.pdf} +\includegraphics{CircFailure-WinMid.pdf} +\caption{Circuit failure of Windows nodes} +\label{fig:WinFail} +\end{figure} + +The Windows node result is not entirely surprising, as it is known that these +nodes will have difficulty servicing large numbers of sockets using normal +WinSock~\cite{nickm-iocp}. As can be seen in Figure \ref{fig:WinFail}, these +nodes exhibit significantly higher circuit failure rates than non-Windows +nodes, and also predictably fare worse in either the Guard or Exit position, +where they have to maintain significantly more TCP sockets for clients and +exit streams, respectively. + +There are some aberrations. In particular, the high-end Windows nodes seem to +be on par with their peers. This is likely due to the higher socket limits of +server editions of Windows as compared to desktop. + +\begin{figure}[htp] +\centering +\includegraphics{CircFailure-BwLimit2.pdf} +\includegraphics{Extends-BwLimit2.pdf} +\caption{Circuit failure and extend times of bandwidth limited vs non-limited +nodes} +\label{fig:BwLimited} +\end{figure} + +Interestingly, as can be seen in the left side of Figure \ref{fig:BwLimited}, +nodes that have configured a specific bandwidth rate limit are considerably +more reliable than those that set no limit and just fill their upstream to the +max. One potential reason for this could be that due to Tor's multiplexing of +streams inside TCP, the backoff properties of TCP are really damaging to the +ability of circuit creation cells to get through in time. Other possibilities +include asymmetric bandwidth limits and OS and CPU limits being easier to hit, +causing failure as opposed to smooth throttling. + +Also of interest from the right side of Figure \ref{fig:BwLimited} is the fact +that despite only emptying their queues once per second, the circuit extend +latencies of bandwidth-limited nodes are still typically less than their +non-limited neighbors. This indicates that most of these rate limited nodes +have more than one second worth of data queued up. It also again hints at the +possibility that the normal fairness properties of TCP are not functioning +properly for the non-limited nodes. + +Additional scans have also shown that unlike the Windows nodes, non-limited +nodes exhibit the same failure characteristics in both middle and Guard/Exit +positions. Furthermore, more failures are caused by timeout as opposed to +closed connections for the non-limited nodes than for the Windows nodes. These +two facts seem to indicate that the circuit failure is independent of the +ability to make a TCP connection for non-limited nodes, and is possibly tied +to the ability to transfer a create cell through the network and also +implicate TCP flow control issues. + +\begin{figure}[htp] +\centering +\includegraphics{CircFailure-LimitWin.pdf} +\includegraphics{CircFailure-WinLimit.pdf} +\caption{Circuit failure of Windows versus Non-Limited nodes} +\label{fig:LimitFail} +\end{figure} + +It is also the case that many of the Windows nodes also do not set +bandwidth limits for themselves. This led us to perform four scans to compare +the effect of Windows, the results of which are shown in Figure \ref{fig:LimitFail}. + +On the left side of Figure \ref{fig:LimitFail}, it can be seen that while +non-Win32 non-limited nodes do exhibit higher failure rates than the limited +nodes in Figure \ref{fig:BwLimited}, the bulk of the failure is due to the +Windows non-limited nodes. Furthermore, on the right of Figure +\ref{fig:LimitFail}, it can be seen that Limited Windows nodes perform +significantly better than non-limited, though again not quite on par with +limited nodes from Figure \ref{fig:BwLimited}. This could be due to the +limited nodes' operators ensuring that they set their bandwidth rate below the +point at which Tor begins to experience performance problems or otherwise slow +down their system. + +This seems to indicate that we need to encourage node operators to set +bandwidth limits below their connection's capacity, and that we need to ensure +that the Vidalia UI is clear enough for Windows users to be able to set +limits properly, and understand the importance of doing so. + +\begin{figure}[htp] +\centering +\includegraphics{BadNodes.pdf} +\includegraphics{BadNodesWin.pdf} +\caption{Density of non-limited and Windows nodes per percentile} +\label{fig:BadNodes} +\end{figure} + +To help understand the effects on the network as a whole, we broke down the +proportion of non-limited and Windows nodes in each percentile slice in Figure +\ref{fig:BadNodes}. On the left is the combination of non-limited and Windows +nodes, and on the right is Windows nodes that are non-limited. It can be seen +that the amount of Windows non-limited nodes roughly correspond to the level +of failure rates from the right side of Figure \ref{fig:Failure}. Of course, +correlation does not imply causation, but it does give us a starting point to +work with. + +\subsection{Directory Feedback} + +Trying to determine the source of unbalancing by guesswork, measurement, and +experiment is time consuming. Correcting for these discovered issues +algorithmically is even harder, and is also fragile to other changes in the +network. + +It would be much better if we could use a balancing metric or metrics, and use +them directly to alter client load allocation to correct for arbitrary +unbalancing. + +\begin{figure}[htp] +\centering +\includegraphics{StreamBwBar2.pdf} +\caption{Stream bandwidth capacity as measured by recent feedback scan} +\label{fig:StreamBw} +\end{figure} + +In a well-balanced network, all streams should receive the same bandwidth. +It can clearly be seen from Figure \ref{fig:StreamBw} that this is not the +case, and that some segments of the network are providing clients with +much better capacities than others. + +Based on this, a good metric to gauge the load of a node relative to its peers +should be the ratio of its average stream capacity to that of the rest of the +network. This ratio should represent the ratio of extra load the node is +carrying over its peers. + +The TorCtl SpeedRacer utility produces these ratios. It divides the network +into 50 node slices based on advertised bandwidth rankings and repeatedly +fetches a large file through 2-hop Tor circuits created inside this range. + +It then uses the SQL support of TorCtl to produce a preliminary ratio for each +node. To prevent potential sabotage and to preserve fairness, nodes with +ratios significantly less than 1.0 are filtered from the results of other +nodes, as are any other slow outlier streams, and the ratios are +recomputed. + +These ratios can then be used to form a feedback loop with the directory +authorities: a set of scanning authorities will use the ratios to adjust node +bandwidths in their consensus document while retaining the original values in +the node descriptors. The authorities will then vote on the official values by +taking the median of the scanning authority values. + +Newer Tor clients (v0.2.1 and above) have already been modified to accept +these new values as part of work done by Peter Palfrader to reduce descriptor +size and directory server overhead. The weighted values will cause these new +clients to choose these nodes less often, due to the probabilistic weighting +of Tor's node selection algorithm~\cite{path-spec}. + +Subsequent passes of the scanner will then use the published value when +computing new ratios, and their computed ratios should eventually converge to +1.0. + +Because we keep the original values on-hand, we can implement algorithmic +balancing improvements in tandem with this system without jeopardizing the +network. All we need to do is see if the new algorithmic changes alter the +ratios that are being computed for better or for worse. + +It should be noted that it is also possible to similarly compute circuit +failure ratios that can be multiplied with the stream capacity ratios to deal +with nodes experiencing forms of load other than bandwidth constraint, such as +those in the preceding section. Our current plan is to perform the stream +adjustments first, and note what effect, if any, this has on circuit +reliability, and then introduce those ratio adjustments if needed. + +\section{Exit Node Scanning} + +The Snakes on a Tor exit scanner performs a series of actions via various exit +nodes. The current implementation was initially written by Google Summer of +Code student Aleksei Gorny. It supports scanning exit nodes for modifications +to SSL, HTML, JavaScript, HTTP Headers, and arbitrary HTTP content. + +Target sites are obtained by querying Google and Yahoo for keywords from a +keyword file and pulling a random selection from those results. + +All aspects of the scan are continually checkpointed and serialized as pickled +Python objects, so that scans can be resumed at any time in the event of code +modification or failure. A Snake Inspector script examines the pickled +results and is able to display error classification and differences in a human +readable format, as well as re-evaluate failures based on changing criteria. + +\subsection{Goals} + +We face a similar problem scope to antivirus software. It is unreasonable to +expect to be able to detect all malicious exit nodes on the network. Nodes can +target specific sites in languages the scanners do not speak, or they can +target only specific users. + +Instead, our goals are essentially twofold: Firstly, we aim for the more +modest goal of removing exit status of misconfigured or egregiously censored +nodes. Second, we aim to prevent dragnet user exploitation and unmasking via +Tor. We want to make it such that there is a high level of risk and effort +associated with using exploits against large sections of the Tor userbase for +purposes of creating botnets or mining account credentials. + +\subsection{General Methodology} + +\lstset{language=Python} +\begin{lstlisting}[frame=single] + TorResult = PerformFetch(Tor, URL, TorAuthSet) + NonTorResult1 = PerformFetch(NonTorIP1, URL, NonTorAuthSet) + if IsPrefix(TorResult, NonTorResult1): + return FAIL_TRUNCATION + + TorResult = StripIrrelevant(TorResult) + NonTorResult1 = StripIrrelevant(NonTorResult1) + if TorResult == NonTorResult1: + return OK + + NonTorResult2 = PerformFetch(NonTorIP2, URL, TorAuthSet) + NonTorResult2 = StripIrrelevant(NonTorResult2) + + if DifferencePruner: # Difference Pruning Step (optional) + Diffs |= Diff(NonTorResult1, NonTorResult2) + NonTorResult2 = Prune(NonTorResult2, Diffs) + TorResult = Prune(TorResult, Diffs) + + if NonTorResult2 == TorResult: + return OK + return FAIL_MODIFICATION +\end{lstlisting} + +In general, all scans follow the pattern in the above pseudocode: +First they perform an operation without Tor. They then perform that same +operation through Tor. If the relevant content matches, it is a success. +Otherwise, they perform the operation again from a new Non-Tor IP but using +the same credentials (such as cookies) that were used during Tor. Optionally, +they perform a "Difference Pruning" step that removes items that have changed +between the two Non-Tor operations from consideration from the second Non-Tor +fetch. Finally, they compare the Tor fetch to this new Non-Tor fetch. If there +are no relevant differences, then it is a success. Otherwise, the node is +marked as a failure. + +In reality, we have many more failure types than just truncation and +modification. There are also DNS failures, various types of network errors, +timeout errors, HTTP errors, SSL errors, Tor errors, and also +subclassifications of these. + +\subsection{HTML and JavaScript Scanning} + +In the case of HTML scanning, we use Beautiful Soup~\cite{BeautifulSoup} to +strip content down to only tags that can contain plugins, script, or CSS in +order to eliminate localization and content changes from comparison and to +obtain a set of page script, iframe, object, and link tags for recursion. + +% XXX: This needs to be more precise +The Difference Pruning step is done by first building sets of HTML tags and +their attributes seen for a particular URL. If any new tags or attributes +appear during successive Non-Tor fetches, they are added to the set of +differences, elements of which then set-subtracted from the Tor fetches. + +The HTML Difference Pruner objects persist for the duration of the scan and +are also serialized, so that differences can continue to be accumulated and +filtered out, and that initial failures can be corrected by the Snake +Inspector script post-scan. + +If the HTML Difference Pruner finds no new Tor differences after pruning, we +rerun the unpruned fetches through a JavaScript Difference Pruner that uses a +Javascript parser from the Antlr Project~\cite{Javascript.g} to prune +differences from an AST. This is done to ensure we haven't pruned a tag or +attribute that varies because of minor Javascript differences (such as unique +identifiers embedded in script). If no Tor differences remain, the node has +passed. + +The Javascript parser and Javascript Difference Pruner are also used for pure +Javascript files during page element recursion. + +\subsection{Filtering False Positives} + +Despite the above efforts, false positives inevitably arise. To deal with +them, we have implemented URL-based filters such that if a particular URL +causes more than a set percentage of exit nodes to fail a scan, it is +automatically removed from consideration and the nodes are rescanned with +fresh URLs. + +Additionally, SoaT provides the ability to rescan nodes that were marked as +failed during any of its previous scans. + +\subsection{Results} + +By far the most common result are nodes that simply routinely timeout instead +of completing streams. A close second to this are nodes that truncate streams +part of the way through. Less common, but still prevalent, are nodes that +cannot perform DNS resolution. There's also usually one or two nodes injecting +Javascript that hooks window.open, presumably as part of their antivirus +software's popup blocking mechanism. On occasion, we'll hit a node that has +some sort of payment portal up, possibly due to people doing things like +attempting to run Tor nodes out of fee-based Internet services in hotels, +coffeshops, or airports. + +On the more malicious end of the spectrum, we've seen a couple of nodes that +spoof SSL, typically with self-signed SSL certificates. Usually these are in +China, but we have seen one in Europe, and another in Atlanta, Georgia. We've +also seen one instance of a node spoofing SSH keys. + +\section{Future Work} + +There are several directions for immediate and long-term future work. + +\subsection{Exit Scanning} + +Despite our efforts, exit scanning still has a number of weaknesses against +diligent adversaries. + +Firstly, we currently have no ability to recursively fetch URLs constructed by +Javascript, which means that if an adversary were able to detect any fetches +generated through them, they would be able to modify the resulting content in +only these URLs without fear of us noticing. The best way to gain full +visibility of these URLs is to actually have a real Firefox instance +controlled by SoaT that gives us a list of URLs to recurse from a given source +URL. We could also extend this to use Firefox to perform additional Tor +fetches from an instrumented virtual machine that actually watches for signs +of proxy bypass, unauthorized disk access, or new executable mappings in the +Firefox process itself. + +Second, we have no visibility behind POST requests and forms. We need to +figure out a way to either randomly post at forms, or use fixed logins for a +set of non-SSL webapps. + +Third, we currently have very limited visibility into websites that are highly +dynamic. In particular, websites that produce completely different layouts for +different countries are often removed from consideration by our URL based +filters. One thing we can do about this is have country-specific scanners that +use GeoIP path restrictions to only scan exits in their own country. Another +might be to delegate trusted exit nodes in each location that can be used to +fetch content where we normally used the local IP. + +Another more serious issue along these lines are the ad networks. Some of them +exhibit too many changes for our difference pruner to be left with much useful +content, and thus may be potentially replaced with malicious content and still +be undetected by our scans. Shipping something like Adblock in the default +configuration of Tor would essentially eliminate this from our threat model +(and make our users safer in general, as the ad networks themselves are often +vectors for malware~\cite{ads-malware}). However, this may introduce political +complications. Many sites are already trigger-happy to ban the entire Tor +network from contributing content, and a loss of revenue stream may be all the +reason they need to ban readers as well. + +Fourth, it would be interesting to set up some honeypot accounts that log in +to POP3 and IMAP accounts only from specific exit IPs, to determine if these +accounts are ever used outside of the scan. + +\subsection{Reliability and Node-Based Directory Feedback} + +As we've seen, stream capacity is not the whole story when it comes to node +load. Nodes can become CPU or file descriptor constrained, both of which will +cause them to fail circuits but still have reasonable capacity for those that +get through. In fact, many of the faster nodes on the network max out CPU +before network capacity, which will cause them to drop create cells and close +circuits. However, the circuits and streams that do manage to get through will +have good capacity through these nodes. Does this mean we should weight them +higher, or should we possibly multiply their stream ratio by an additional +circuit failure ratio? + +Along these lines, there is another class of adversary that we'd like to be +able to detect as well: Those that fail circuits that don't involve their +colluding peers~\cite{fu-bh09}. Such adversaries can lie about their bandwidth +capacity by an amount that is proportional to the amount of circuits that they +fail~\cite{mccoy-low,tabriz-denial}, and would able to ensure that every byte +they devote to Tor is devoted to surveiling a compromised path. Worse, their +inflated bandwidth statistics would not be noticed by our capacity scanners +because they would be able to lie just enough to compensate for the circuits +they fail that are not compromised. + +It is our intuition that our reliability statistics can help detect these +attacks, but to have a truly resilient defense, we'd need node based monitoring +of circuit reliability as opposed to client based, which is prone to +fingerprinting and detection. + +\subsection{We Need More Data!} + +We've only just begun to leverage the new TorCtl framework, and for every +question it answers, there are often two more uncovered as a result. More +scans need to be done to test various hypotheses to attempt to answer these +questions. + +In particular, the circuit construction scans that shed insight into +particular trouble-spots in the network should also be repeated as stream +capacity scans. Because stream capacity scans are considerably slower and more +taxing on the network, it was much easier to find the trouble spots with +circuit scans first. However, certain characteristics may affect circuit +failure and not stream capacity and vice-versa, so all of the pertinent +results should ideally be repeated with stream bandwidth scans. + +\section{Acknowledgments} + +We'd like to thank all of our Google Summer of Code students who have +contributed various features to TorFlow: Johannes Renner for his GeoIP-based +restrictions and his work in building latency maps of the Tor network, Fallon +Chen for her work on the BuildTimes utility, and Aleksei Gorny for his work +on an initial Python rewrite of SoaT. We'd also like to thank Google for +sponsoring Tor and providing a generous allocation of students year after +year. + +We'd also like to thank Karsten Loesing for his thorough analysis of our +circuit BuildTimes data and for his Python rewrite of the URL fetching +piece of SpeedRacer. + +Lastly, we'd like to thank Roger and Nick for having the foresight to design +such a flexible control mechanism for Tor, for their thorough efforts at +documenting it and the rest of Tor, and for Tor in general. + +\bibliographystyle{plain} \bibliography{torflow} + +\clearpage +\appendix + +\end{document} diff --git a/2009/torflow/usenix.sty b/2009/torflow/usenix.sty new file mode 100644 index 0000000..31cebc0 --- /dev/null +++ b/2009/torflow/usenix.sty @@ -0,0 +1,96 @@ +% usenix-2e.sty - to be used with latex2e (the new one) for USENIX. +% To use this style file, do this: +% +% \documentclass[twocolumn]{article} +% \usepackage{usenix-2e} +% and put {\rm ....} around the author names. +% +% The following definitions are modifications of standard article.sty +% definitions, arranged to do a better job of matching the USENIX +% guidelines. +% It will automatically select two-column mode and the Times-Roman +% font. + +% +% USENIX papers are two-column. +% Times-Roman font is nice if you can get it (requires NFSS, +% which is in latex2e. + +%\if@twocolumn\else\input twocolumn.sty\fi +\usepackage{times} + +% +% USENIX wants margins of: 7/8" side, 1" bottom, and 3/4" top. +% 0.25" gutter between columns. +% Gives active areas of 6.75" x 9.25" +% +\setlength{\textheight}{9.0in} +\setlength{\columnsep}{0.25in} +%%\setlength{\textwidth}{6.75in} +\setlength{\textwidth}{7.00in} +%\setlength{\footheight}{0.0in} +\setlength{\topmargin}{-0.25in} +\setlength{\headheight}{0.0in} +\setlength{\headsep}{0.0in} +\setlength{\evensidemargin}{-0.125in} +\setlength{\oddsidemargin}{-0.125in} + +% +% Usenix wants no page numbers for submitted papers, so that they can +% number them themselves. +% +\pagestyle{empty} + +% +% Usenix titles are in 14-point bold type, with no date, and with no +% change in the empty page headers. The whol author section is 12 point +% italic--- you must use {\rm } around the actual author names to get +% them in roman. +% +\def\maketitle{\par + \begingroup + \renewcommand\thefootnote{\fnsymbol{footnote}}% + \def@makefnmark{\hbox to\z@{$\m@th^{@thefnmark}$\hss}}% + \long\def@makefntext##1{\parindent 1em\noindent + \hbox to1.8em{\hss$\m@th^{@thefnmark}$}##1}% + \if@twocolumn + \twocolumn[@maketitle]% + \else \newpage + \global@topnum\z@ + @maketitle \fi@thanks + \endgroup + \setcounter{footnote}{0}% + \let\maketitle\relax + \let@maketitle\relax + \gdef@thanks{}\gdef@author{}\gdef@title{}\let\thanks\relax} + +\def@maketitle{\newpage + \vbox to 2.5in{ + \vspace*{\fill} + \vskip 2em + \begin{center}% + {\Large\bf @title \par}% + \vskip 0.375in minus 0.300in + {\large\it + \lineskip .5em + \begin{tabular}[t]{c}@author + \end{tabular}\par}% + \end{center}% + \par + \vspace*{\fill} +% \vskip 1.5em + } +} + +% +% The abstract is preceded by a 12-pt bold centered heading +\def\abstract{\begin{center}% +{\large\bf \abstractname\vspace{-.5em}\vspace{\z@}}% +\end{center}} +\def\endabstract{} + +% +% Main section titles are 12-pt bold. Others can be same or smaller. +% +\def\section{@startsection {section}{1}{\z@}{-3.5ex plus-1ex minus + -.2ex}{2.3ex plus.2ex}{\reset@font\large\bf}}