An Immunological Model of Distributed Detection and Its Application
`to Computer Security
`
`By
`
`Steven Andrew Hofmeyr
`
`B.Sc. (Hons), Computer Science, University of the Witwatersrand, 1991
`M.Sc., Computer Science, University of the Witwatersrand, 1994
`
`Doctor of Philosophy
`Computer Science
`
`May 1999
`
`DivX, LLC Exhibit 2011
`Page 2011 - 1
`Netflix Inc. et al. v. DivX, LLC, IPR2020-00614
`
`

`

`DivX, LLC Exhibit 2011
`Page 2011 - 2
`Netflix Inc. et al. v. DivX, LLC, IPR2020-00614
`
`

`

`c 1999, Steven Andrew Hofmeyr
`
`iii
`
`DivX, LLC Exhibit 2011
`Page 2011 - 3
`Netflix Inc. et al. v. DivX, LLC, IPR2020-00614
`
`

`

`DivX, LLC Exhibit 2011
`Page 2011 - 4
`Netflix Inc. et al. v. DivX, LLC, IPR2020-00614
`
`

`

`Dedication
`
`To the Babs for having such patience when I was so far away, and to my dearest Folks for getting me this far.
`
`v
`
`DivX, LLC Exhibit 2011
`Page 2011 - 5
`Netflix Inc. et al. v. DivX, LLC, IPR2020-00614
`
`

`

`DivX, LLC Exhibit 2011
`Page 2011 - 6
`Netflix Inc. et al. v. DivX, LLC, IPR2020-00614
`
`

`

`Acknowledgments
`
`The author gratefully acknowledges the help of the following people: D. Ackley, P. D’haeseleer, S. Forrest,
`G. Hunsicker, S. Janes, T. Kaplan, J. Kephart, B. Maccabe, M. Oprea, B. Patel, A. Perelson, D. Smith, A.
`Somayaji, G. Spafford, and all the people in the Adaptive Computation Group at the University of New
`Mexico.
`
`This research was supported by the Defense Advanced Research Projects Agency (grant N00014-96-
`1-0680) the National Science Foundation (grant IRI-9711199), the Office of Naval Research (grant N00014-
`99-1-0417), the IBM Partnership award, and the Intel Corporation.
`
`STEVEN HOFMEYR
`
`TheUniversityofNewMexico
`May1999
`
`vii
`
`DivX, LLC Exhibit 2011
`Page 2011 - 7
`Netflix Inc. et al. v. DivX, LLC, IPR2020-00614
`
`

`

`DivX, LLC Exhibit 2011
`Page 2011 - 8
`Netflix Inc. et al. v. DivX, LLC, IPR2020-00614
`
`

`

`An Immunological Model of Distributed Detection and Its Application
`to Computer Security
`
`By
`
`Steven Andrew Hofmeyr
`
`Doctor of Philosophy
`Computer Science
`
`May 1999
`
`DivX, LLC Exhibit 2011
`Page 2011 - 9
`Netflix Inc. et al. v. DivX, LLC, IPR2020-00614
`
`

`

`DivX, LLC Exhibit 2011
`Page 2011 - 10
`Netflix Inc. et al. v. DivX, LLC, IPR2020-00614
`
`

`

`An Immunological Model of Distributed Detection and Its Application
`to Computer Security
`
`by
`
`Steven Andrew Hofmeyr
`
`B.Sc. (Hons), Computer Science, University of the Witwatersrand, 1991
`M.Sc., Computer Science, University of the Witwatersrand, 1994
`Ph.D., Computer Science, University of New Mexico, 1999
`
`Abstract
`
`This dissertation explores an immunological model of distributed detection, called negative detec-
`tion, and studies its performance in the domain of intrusion detection on computer networks. The goal of the
`detection system is to distinguish between illegitimate behaviour (nonself ), and legitimate behaviour (self ).
`The detection system consists of sets of negative detectors that detect instances of nonself; these detectors are
`distributed across multiple locations. The negative detection model was developed previously; this research
`extends that previous work in several ways.
`Firstly, analyses are derived for the negative detection model. In particular, a framework for explicitly
`incorporating distribution is developed, and is used to demonstrate that negative detection is both scalable and
`robust. Furthermore, it is shown that any scalable distributed detection system that requires communication
`(memory sharing) is always less robust than a system that does not require communication (such as negative
`detection).
`In addition to exploring the framework, algorithms are developed for determining whether a
`nonself instance is an undetectable hole, and for predicting performance when the system is trained on non-
`random data sets. Finally, theory is derived for predicting false positives in the case when the training set
`does not include all of self.
`Secondly, several extensions to the model of distributed detection are described and analysed. These
`extensions include: multiple representations to overcome holes; activation thresholds and sensitivity levels to
`reduce false positive rates; costimulation by a human operator to eliminate autoreactive detectors; distributed
`detector generation to adapt to changing self sets; dynamic detectors to avoid consistent gaps in detection
`coverage; and memory, to implement signature-based detection.
`Thirdly, the model is applied to network intrusion detection. The system monitors TCP traffic in
`a broadcast local area network. The results of empirical testing of the model demonstrate that the system
`detects real intrusions, with false positive rates of less than one per day, using at most five kilobytes per
`computer. The system is tunable, so detection rates can be traded off against false positives and resource
`usage. The system detects new intrusive behaviours (anomaly detection), and exploits knowledge of past
`intrusions to improve subsequent detection (signature-based detection).
`
`xi
`
`DivX, LLC Exhibit 2011
`Page 2011 - 11
`Netflix Inc. et al. v. DivX, LLC, IPR2020-00614
`
`

`

`DivX, LLC Exhibit 2011
`Page 2011 - 12
`Netflix Inc. et al. v. DivX, LLC, IPR2020-00614
`
`

`

`Contents
`
`List of Figures
`
`List of Tables
`
`Glossary of Symbols
`
`1 Introduction
`. . . .
`. . . .
`. . . .
`. . .
`1.1
`Immunology . .
`. . . .
`. . . .
`. . . .
`1.2
`Computer Security . .
`1.3
`Principles for an Artificial Immune System .
`1.4
`The Contributions of this Dissertation . . . .
`1.5
`The Remainder of this Dissertation .
`. . . .
`
`. . .
`. . .
`. . .
`. . .
`. . .
`
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`
`. . .
`. . .
`. . .
`. . .
`. . .
`
`. . .
`. . .
`. . .
`. . .
`. . .
`
`2 Background
`. . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . .
`2.1
`Immunology for Computer Scientists . . . .
`. . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . .
`2.1.1
`Recognition . . . .
`. . . .
`. . . .
`. . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . .
`2.1.2
`Receptor Diversity .
`. . . .
`. . . .
`. . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . .
`2.1.3
`Adaptation .
`. . . .
`. . . .
`. . . .
`. . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . .
`2.1.4
`Tolerance . .
`. . . .
`. . . .
`. . . .
`. . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . .
`2.1.5 MHC and diversity .
`. . . .
`. . . .
`A First Attempt at Applying Immunology to ID: Host-based Anomaly Detection . . .
`Network Intrusion Detection . . . .
`. . . .
`. . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . .
`2.3.1
`Networking and Network Protocols . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . .
`2.3.2
`Network Attacks . .
`. . . .
`. . . .
`. . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . .
`2.3.3
`A Survey of Network Intrusion Detection Systems . . .
`. . . .
`. . . .
`. . .
`2.3.4
`Building on Network Security Monitor .
`. . . .
`. . . .
`. . . .
`. . . .
`. . .
`2.3.5
`Desirable Extensions to NSM . . .
`. . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . .
`An Immunologically-Inspired Distributed Detection System . . .
`. . . .
`. . . .
`. . .
`
`2.2
`2.3
`
`2.4
`
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`
`3 An Immunological Model of Distributed Detection
`3.1
`Properties of The Model . . .
`. . . .
`. . . .
`. . .
`3.1.1
`Problem Description . . . .
`. . . .
`. . .
`3.1.2
`Distributing the Detection System .
`. . .
`3.1.3
`Assumptions . . . .
`. . . .
`. . . .
`. . .
`3.1.4
`Generalization . . .
`. . . .
`. . . .
`. . .
`3.1.5
`Scalable Distributed Detection . .
`. . .
`
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`
`xiii
`
`xvi
`
`xviii
`
`xix
`
`1
`1
`2
`4
`5
`5
`
`7
`7
`8
`10
`10
`11
`14
`15
`16
`16
`17
`19
`20
`21
`21
`
`23
`23
`23
`24
`25
`26
`26
`
`DivX, LLC Exhibit 2011
`Page 2011 - 13
`Netflix Inc. et al. v. DivX, LLC, IPR2020-00614
`
`

`

`Robust Distributed Detection . . .
`3.1.6
`Implementation and Analysis . . . .
`. . . .
`3.2.1 Match Rules . . . .
`. . . .
`. . . .
`3.2.2
`Detector Generation . . . .
`. . . .
`3.2.3
`Detector Sets . . . .
`. . . .
`. . . .
`3.2.4
`The Existence of Holes
`. .
`. . . .
`3.2.5
`Refining the Analysis
`. . .
`. . . .
`3.2.6 Multiple Representations
`.
`. . . .
`3.2.7
`Incomplete Training Sets
`.
`. . . .
`Summary . . . .
`. . .
`. . . .
`. . . .
`. . . .
`
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`
`3.2
`
`3.3
`
`4 An Application of the Model: Network Security
`. . . .
`. . . .
`. . .
`4.1
`Architecture . .
`. . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . .
`4.1.1
`Base Representation . . . .
`. . . .
`. . . .
`. . . .
`. . .
`4.1.2
`Secondary Representations
`. . . .
`. . . .
`4.1.3
`Activation Thresholds and Sensitivity Levels . .
`. . . .
`Experimental Data Sets . . .
`. . . .
`. . . .
`. . .
`. . . .
`. . . .
`. .
`. . . .
`. . .
`. . . .
`4.2.1
`. . . .
`4.2.2
`. .
`. . . .
`. . .
`. . . .
`. . . .
`. . . .
`Experimental Results
`. . . .
`. . . .
`. . .
`. . . .
`. . . .
`4.3.1
`Generating the detector sets . . . .
`. . .
`. . . .
`. . . .
`4.3.2 Match Rules and Secondary Representations . .
`4.3.3
`The Effects of Multiple Secondary Representations . . .
`4.3.4
`Incomplete Self Sets . . . .
`. . . .
`. . .
`. . . .
`. . . .
`4.3.5
`Detecting Real Nonself
`. .
`. . . .
`. . .
`. . . .
`. . . .
`4.3.6
`Increasing the Size of the Self Set .
`. . .
`. . . .
`. . . .
`Summary . . . .
`. . .
`. . . .
`. . . .
`. . . .
`. . .
`. . . .
`. . . .
`
`4.2
`
`4.3
`
`Self Sets,  and  
`
`Nonself Test Sets,

 
`
`
`4.4
`
`5 Extensions to the Basic Model
`. . . .
`5.1
`The Mechanisms . . .
`. . . .
`. . . .
`5.1.1
`Costimulation . . .
`5.1.2
`Distributed Tolerization . .
`5.1.3
`Dynamic Detectors .
`. . . .
`5.1.4 Memory . .
`. . . .
`. . . .
`5.1.5
`Architectural Summary . .
`Experimental Results
`. . . .
`. . . .
`5.2.1
`Costimulation . . .
`. . . .
`5.2.2
`Changing Self Sets .
`. . . .
`5.2.3 Memory . .
`. . . .
`. . . .
`Summary . . . .
`. . .
`. . . .
`. . . .
`
`5.2
`
`5.3
`
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`
`27
`29
`30
`31
`33
`35
`37
`39
`42
`43
`
`44
`45
`45
`47
`48
`49
`50
`51
`52
`53
`55
`55
`62
`64
`66
`69
`
`71
`71
`72
`72
`75
`75
`76
`78
`79
`80
`86
`89
`
`90
`90
`90
`94
`95
`95
`
`6 Implications and Consequences
`6.1
`Giving Humans a Holiday: Automated Response .
`6.1.1
`Adaptive TCP Wrappers . .
`. . . .
`. . .
`6.1.2
`Fighting Worms with Worms
`. . .
`. . .
`Other Applications . .
`. . . .
`. . . .
`. . . .
`. . .
`6.2.1 Mobile Agents . . .
`. . . .
`. . . .
`. . .
`
`6.2
`
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`
`. . .
`. . .
`. . .
`. . .
`. . .
`
`. . .
`. . .
`. . .
`. . .
`. . .
`
`xiv
`
`DivX, LLC Exhibit 2011
`Page 2011 - 14
`Netflix Inc. et al. v. DivX, LLC, IPR2020-00614
`
`

`

`6.3
`
`. . . .
`Distributed Databases . . .
`6.2.2
`. . . .
`Implications of the Analogy .
`. . . .
`6.3.1
`Understanding Immunology . . . .
`6.3.2
`Insights for Computer Science . . .
`
`. . .
`. . .
`. . .
`. . .
`
`. . . .
`. . . .
`. . . .
`. . . .
`
`. . . .
`. . . .
`. . . .
`. . . .
`
`. . . .
`. . . .
`. . . .
`. . . .
`
`. . . .
`. . . .
`. . . .
`. . . .
`
`. . .
`. . .
`. . .
`. . .
`
`96
`. . .
`99
`. . .
`99
`. . .
`. . . 100
`
`7 Conclusions
`. . . .
`. . . .
`7.1
`Principles Attained . .
`7.2
`Contributions of this Dissertation . .
`7.3
`Limitations of this Dissertation . . .
`7.4
`Future Work . .
`. . .
`. . . .
`. . . .
`7.5
`A Final Word .
`. . .
`. . . .
`. . . .
`
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`
`. . .
`. . .
`. . .
`. . .
`. . .
`
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`
`. . . .
`. . . .
`. . . .
`. . . .
`. . . .
`
`. . .
`. . .
`. . .
`. . .
`. . .
`
`References
`
`102
`. . . 102
`. . . 103
`. . . 104
`. . . 105
`. . . 107
`
`109
`
`xv
`
`DivX, LLC Exhibit 2011
`Page 2011 - 15
`Netflix Inc. et al. v. DivX, LLC, IPR2020-00614
`
`

`

`List of Figures
`
`2.1
`2.2
`2.3
`2.4
`2.5
`
`.
`Detection is a consequence of binding between complementary chemical structures
`Responses in immune memory . . .
`. . . .
`. . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . .
`Associative memory underlies the concept of immunization . . .
`. . . .
`. . . .
`. . .
`The three-way TCP handshake for establishing a connection . . .
`. . . .
`. . . .
`. . .
`Patterns of network traffic on a broadcast LAN . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . .
`
`. . .
`. . .
`. . .
`. . .
`. . .
`
`. . .
`. . . .
`. . . .
`The universe of patterns . . .
`3.1
`3.2 Matching under the contiguous bits match rule . .
`3.3
`The negative selection algorithm . .
`. . . .
`. . .
`3.4
`
`. . .
`. . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . .
`. . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . .
`. . .
`. . . .
`. . . .
`. . . .
`. . . .
`, and the expected number of retries
`. . . .
`. . . .
`. . . .
`. . . .
`. . .
`. . .
`. . .
`. . . .
`. . . .
`. . . .
`. . .
`. . . .
`. .
`. . . .
`. . . .
`. . . .
`. . . .
`. . .
`. . .
`. . .
`. . . .
`. . . .
`The existence of holes . . . .
`. . .
`. . . .
`. . . .
`. . . .
`. . .
`. . .
`Searching the RHS string space for a valid detector
`Representation changes are equivalent to “shape” changes for detectors .
`. . . .
`. . .
`. . .
`
`The trade-off between number of detectors required,
`
`
`3.5
`3.6
`3.7
`
`9
`12
`13
`18
`20
`
`24
`30
`32
`
`34
`35
`37
`41
`
`.
`Base representation of a TCP SYN packet
`Substring hashing . .
`. . . .
`. . . .
`. . . .
`Sample distribution of self strings . .
`. . . .
`
`. . .
`. . .
`. . .
`
`. . . .
`. . . .
`. . . .
`
`. . . .
`. . . .
`. . . .
`
`. . . .
`. . . .
`. . . .
`
`. . . .
`. . . .
`. . . .
`
`. . .
`. . .
`. . .
`
`. . .
`. . .
`. . .
`
`46
`48
`50
`
`. . . .
`
`. . . .
`
`. . . .
`
`. . .
`
`. . . .
`
`. . . .
`
`. . . .
`
`. . . .
`
`. . .
`
`. . .
`
`56
`
`. .
`
`. . . .
`
`. . . .
`
`. . .
`
`. . . .
`
`. . . .
`
`. . . .
`
`. . . .
`
`. . .
`
`. . .
`
`57
`
`4.1
`4.2
`4.3
`4.4
`4.5
`
`4.6
`
`4.7
`
`4.8
`4.9
`
`. . . .
`
`. . . .
`
`. . . .
`
`. . .
`
`. . . .
`
`. . . .
`. . . .
`
`. . . .
`. . . .
`
`. . . .
`
`. . . .
`. . . .
`. . . .
`. . . .
`. .
`
`Expected number of retries, , for tolerization versus match length,
`( varies, none) 54
`Trade-offs for different match rules and secondary representations on SE (! #" , varies,
` varies,$ varies) . .
`Trade-offs for different match rules and secondary representations on RND (%& '" ,
`varies, varies,$ varies)
`Trade-offs for different match rules and secondary representations on SI (  ( '" , varies,
` varies,$ varies) . .
`The distribution of detection rates on SI (*)+( '"," ) . . .
`Predicting- using the modified simple theory (( '" , varies) . . . .
`4.10 Predicting-
`for SI using the modified simple theory ( varies) .
`4.11 The effect of activation thresholds on false positive rates for  
` (. varies)
`4.12 How the number of detectors impacts on detection rate (  varies,.! '" ) . . .
`4.13 ROC curve for this system (. varies)
`
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`. . .
`
`58
`60
`61
`62
`64
`65
`67
`68
`
`77
`78
`79
`
`. . . .
`. . .
`. . . .
`4.14 Sample distribution of self strings for 120 computers . . .
`
`. . . .
`. . . .
`
`. . . .
`. . . .
`
`. . . .
`. . . .
`
`5.1
`5.2
`5.3
`
`. . . .
`The architecture of the distributed ID system . . .
`. . . .
`The lifecycle of a detector . .
`. . . .
`. . . .
`. . .
`The probability distributions for real and simulated self
`.
`
`. . . .
`. . . .
`. . . .
`
`. . . .
`. . . .
`. . . .
`
`. . . .
`. . . .
`. . . .
`
`. . .
`. . .
`. . .
`
`. . .
`. . .
`. . .
`
`xvi
`
`DivX, LLC Exhibit 2011
`Page 2011 - 16
`Netflix Inc. et al. v. DivX, LLC, IPR2020-00614
`
`

`

`5.4
`
`5.5
`
`5.6
`
`5.7
`
`5.8
`
`82
`
`82
`
`83
`
`84
`
`88
`
`False positive rates over time for a typical run with different tolerization periods, for a mas-
`. . . .
`. . . .
`. . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . .
`. . .
`
`. . .
`. . .
`. . . .
`. . . .
`. . . .
`. . . .
`. . .
`, over time for a typical run with different tolerization periods, for
`.
`. . . .
`. . . .
`. . .
`. . .
`
`. . .
`
`. . .
`
`sive self change (/ varies) . .
`Fraction of immature detectors,0 , over time for a typical run with different tolerization
`periods, for a massive self change (/ varies)
`False positive rates,13254
`a massive self change (/ varies,687:9 ;< >=@?A '"BDCE GFGHJILK )
`Fraction of immature detectors,0 , over time for a typical run with different tolerization
`periods, for a massive self change(/ varies,6 7:9 ;<MN=@?O #"BPCQ( LF5HJILK ) . . .
`False positive rate per day with different tolerization periods (/ varies,6 7:9 ;<R>= ?Q '"JBPCQ GFGHJILK ,S TU9V<3XWYVZM?O #"BD[ ) . . . .
`
`. . . .
`
`. . .
`
`. . . .
`
`. . . .
`
`. . . .
`
`. . . .
`
`. . .
`
`. . .
`
`xvii
`
`DivX, LLC Exhibit 2011
`Page 2011 - 17
`Netflix Inc. et al. v. DivX, LLC, IPR2020-00614
`
`

`

`52
`53
`59
`66
`
`80
`81
`85
`86
`
`87
`
`89
`
`List of Tables
`
`. . . .
`. . .
`. . . .
`. . . .
`. . .
`Features of nonself sets
`The parameters for the basic distributed ID system . . . .
`. . .
`. . . .
`. .
`. . . .
`
`. . . .
`. . . .
`. . . .
`. . . .
`
`. . . .
`. . . .
`. . . .
`. . . .
`
`. . . .
`. . . .
`. . . .
`. . . .
`
`. . .
`. . .
`. . .
`. . .
`
`. . .
`. . .
`. . .
`. . .
`
`4.1
`4.2
`4.3
`4.4
`
`5.1
`5.2
`5.3
`5.4
`5.5
`
`5.6
`
`The effects of nearness (\E '" , varies) .
`Detection rates against real test sets (. varies)
`Costimulation results (. varies,/^] varies)
`Effects of a massive change in the self set (/ varies,6 7:9 ;<M_=@?A '"BDCQE LF5HJILK )
`Effects of a massive change in the self set (/ varies,6 7:9 ;<M_=@?A '"BDCQE LF5HJILK
`,.`W ) .
`Effects of tolerization periods and death probabilities on memory (abcd ,Y" ,/
`S TU9V< varies,6 7:9 ;<MN=@?A '"JBPCQ! GFGHJILK )
`Effects of memory (ae varies,/E(fgW5"g","Rh 'HJILK
`,SiTU9<!WYVZj?k #"BP[3l per 7 days,
`687:9 ;< >=@?A '"BDCQ! GFGHJILK ) . . . .
`
`The parameters for the basic distributed ID system . . . .
`.
`. . .
`. . . .
`
`. . . .
`. . . .
`
`. . . .
`. . . .
`
`. . . .
`. . . .
`
`. . .
`
`. . . .
`
`. . . .
`
`. . . .
`
`. . . .
`
`. . .
`. . .
`.
`
`. . .
`. . .
`. . .
`
`varies,
`. . .
`. . .
`
`. . . .
`
`. . .
`
`. . . .
`
`. . . .
`
`. . . .
`
`. . . .
`
`. . .
`
`. . .
`
`xviii
`
`DivX, LLC Exhibit 2011
`Page 2011 - 18
`Netflix Inc. et al. v. DivX, LLC, IPR2020-00614
`
`

`

`Glossary of Symbols
`
`The symbols are listed in the order in which they appear in the text.
`
`Self set
`
`Detection system memory
`
`m String length
` Match threshold
`n Universe
`

Nonself set
`o Kolmogorov complexity
`p Detection system
`q Binary classification function
`n  
` Test set
`n  Training set
`254
`2sB False negative error
` Number of locations
`ukv Memory capacity at locationwx Global classification function
`254y Global false positive
`2sBy Global false negative
`z Constant
` Representation function
`n|{ Representation ofn
`
`False positive error
`
`Set of locations
`
`xix
`
`DivX, LLC Exhibit 2011
`Page 2011 - 19
`Netflix Inc. et al. v. DivX, LLC, IPR2020-00614
`
`
`r
`t
`

`

`Probability of a match
`
`Parameter set for a representation
`
`Probability of matching under the Hamming match rule
`
`$ Match rule
`}  Cover set of detector~S ;€GVV‚ Probability of matching under the contiguous bits rule
`S <9€7ƒ7
`
`„ … The event that~ does not match any† in {SP‡
`ˆ~  Valid detector~ Number of retries in detector generation
`v Number of detectors at locationwS8‰‹Š Probability of a false negative error
`S8‰Œ Probability of a false positive error
`Ž Algorithm which computes if a given nonself string is a hole
` The overlap function
` Decimal value of binary string remapped by the linear congruential operator
`‘ Parameter for the linear congruential operator
`’ Parameter for the linear congruential operator
`“ Discrete random process
`“@… Random variable of“
`at time-step”•S † Sample distribution of self set
`S † Distribution of self set
`a –€ Number of unique self strings that occur in–
`*) Number of locations
` Number of detectors
`  Training set
`  
` Test set, self strings only
`

 
` Test set, nonself strings only
`˜ Match count for detector~. Activation threshold
`
`time-steps
`
`xx
`
`DivX, LLC Exhibit 2011
`Page 2011 - 20
`Netflix Inc. et al. v. DivX, LLC, IPR2020-00614
`
`—
`

`

`False positive error rate
`
`6 7:9 ;< Match decay probability
`™ v Sensitivity level at locationwš Effect of sensitivity
`6s› Sensitivity decay probability
`1M254
`1M2sB False negative error rate
`- Detection rate
`’ Constant used when predicting retries versus detection rate
`œcž Ÿ¢¡‹ Hamming distance between binary strings and¡-£9€¤V¤ Detection rate over all strings in a nonself incident
`-ƒ5€#
`€¤¥ Detection rate over only the nonself strings in a nonself incident
` Offset in power law distribution of self set
`¡ Exponent in power law distribution of self set
`¦ Ratio of increase in self strings when size of self increases
`/ ] Costimulation delay
`/ Tolerization period
`§ ¨ Queue arrival rate
`§ © Queue departure rate
`¦ Ratio of queue arrivals to departures
`S … Probability of occurrence of a self string,†… Random variable for the number of matches in a queue
`– Match decay period
`SiTU9< Probability of detector death
`0 Fraction of immature detectors
`«ª­¬­®¯L Expected lifetime
`ab Maximum number of memory detectors
`
`xxi
`
`DivX, LLC Exhibit 2011
`Page 2011 - 21
`Netflix Inc. et al. v. DivX, LLC, IPR2020-00614
`
`

`

`DivX, LLC Exhibit 2011
`Page 2011 - 22
`Netflix Inc. et al. v. DivX, LLC, IPR2020-00614
`
`

`

`Chapter 1
`
`Introduction
`
`The Immune System (IS) is complex, and to the observer, has novel solutions for solving real-world prob-
`lems. We can apply this wealth of evolved solutions to systems design if we can find an artificial system that
`faces similar problems to those faced by the IS. To do this we need to have a reasonable understanding of
`immunology.
`
`1.1 Immunology
`
`From a teleological viewpoint, the IS has evolved to solve a particular problem. Fundamentally, such a
`viewpoint is wrong, because the IS is not necessarily a minimal system (there may be simpler ways to solve
`the same problem) but this viewpoint is useful for expository purposes: it is easier to understand the IS to
`a first approximation if the components and mechanisms are viewed with the assumption that they exist to
`solve a particular problem.
`The human body is under constant siege by a plethora of inimical micro-organisms such as bacteria,
`parasites, viruses, and fungi, known collectively as pathogens. These pathogens are the source of many dis-
`eases and ailments, for example, pneumonia is caused by bacteria, AIDS and influenza are caused by viruses,
`and malaria is caused by parasites. Pathogens in particular can be harmful because they replicate, leading to
`a rapid demise of the host if left unchecked. In addition to micro-organisms, the human body is threatened
`by toxic substances that can do serious harm if they are not cleared from the body. In this dissertation it is
`assumed that the “purpose” of the IS is to protect the body from the threats posed by pathogens, and to do so
`in a way that minimizes harm to the body and ensures its continued functioning1.
`There are two aspects to the problem that the IS faces: the identification or detection of pathogens,
`and the efficient elimination of those pathogens while minimizing harm to the body, from both pathogens and
`the IS itself. The detection problem is often described as that of distinguishing “self” from “nonself” (which
`are elements of the body, and pathogens/toxins, respectively). However, many pathogens are not harmful,
`and an immune response to eliminate them may damage the body. In these cases it would be healthier not
`to respond, so it would be more accurate to say that the problem faced by the IS is that of distinguishing be-
`tween harmful nonself and everything else [Matzinger, 1994, Matzinger, 1998]2. Once pathogens have been
`detected, the IS must eliminate them in some manner. Different pathogens have to be eliminated in different
`ways, and the components of the IS that accomplish this are called effectors. The elimination problem facing
`
`

`

`the IS is that of choosing the right effectors for the particular kind of pathogen to be eliminated.
`
`1.2 Computer Security
`
`Phrased this way, the problem that the IS addresses is similar to the problem faced by computer security
`systems: the immune system protects the body from pathogens, and analogously, a computer security system
`should protect computers from intrusions. This analogy can be made more concrete by understanding the
`problems faced by computer security systems. There are several aspects to computer security [Meade, 1985,
`Garfinkel & Spafford, 1996]:
`
`Confidentiality: Access to restricted or confidential data should only be allowed to authorized users, for
`example, it is imperative for military institutions to limit knowledge of classified information.
`
`Integrity: Data should be protected from corruption, whether malicious or accidental. In some cases, it is
`essential to preserve the integrity of critical information, for example, there should be no tampering
`with information used by emergency services.
`
`Availability: Both information and computer resources should be available when needed by legitimate users.
`In particular, this is essential in cases where such information is needed to make critical decisions within
`a limited time, for example, in air-traffic control.
`
`Accountability: In the case where the compromise of a computer system has been detected, the computer
`security system should preserve sufficient information to be able to track down and identify the perpe-
`trators.
`
`Correctness: False alarms from incorrect classification of events should be minimised for the system to be
`usable. Low levels of correctness can interfere with other aspects of security, for example, availability
`will be reduced if a user’s legitimate actions are frequently labeled as alarms, and so not permitted.
`
`The importance of these aspects of computer security depends on the security policy for the computer
`system. The policy is a description or definition of what activities are and are not allowed, by the different
`users and software components of the system. Policy must first be specified by those in charge of the system,
`and then implemented in some form. Both specification and implementation are prone to error, being subject
`to the same limitations as program verification and implementation: programs are not verifiable in general,
`and implementation is always subject to error.
`It is generally agreed that implementing and maintaining secure computer systems is difficult,
`in that we have no way of ensuring that a certain level of security has been achieved [Frank, 1994,
`Crosbie & Spafford, 1994, Kumar & Spafford, 1994, Lunt, 1993, Anderson, et al., 1995, Blakely, 1997]. Se-
`curity holes are exploited by intruders breaking into systems, or by viruses or worms. Such holes are often
`the result of faults or design flaws in system or application software, or in the specification or implementation
`of security policies. Even if it were possible to design and build a completely secure system, the invest-
`ment in systems deployed in the 1990s makes it infeasible to replace every existing system. Furthermore,
`the continual updating of old systems, and the addition of new components will continue to produce novel
`vulnerabilities.
`The similarity between the problem of computer security and that faced by the IS can be shown
`by translating the language of immunology into computer security terms: we can say that the IS detects
`abuses of an implicitly specified policy, and responds to those abuses by counter-attacking the source of the
`abuse. The policy is implicitly specified by natural selection, and emphasises only some aspects of security:
`
`2
`
`DivX, LLC Exhibit 2011
`Page 2011 - 24
`Netflix Inc. et al. v. DivX, LLC, IPR2020-00614
`
`

`

`availability and correctness are of paramount importance, and to a lesser extent, integrity and accountability.
`Availability means enabling the body to continue functioning under an onslaught of pathogens; correctness
`means preventing the IS from attacking the body, (i.e., minimising auto-immune disorders); integrity means
`ensuring that the genes that encode for cell functions are not corrupted by pathogens; and accountability
`means finding and destroying the pathogens responsible for illness3. The one aspect of security that is not
`important to the IS is confidentiality: there is no notion of secret or restricted data in the body that must be
`protected at all costs from outsiders (e.g., we continuously shed cells with our DNA in them.
`The IS is analogous to a computer security system, one that is designed to safeguard against breaches
`in an implicit policy. However, the architecture of the IS is different from that of the computer security sys-
`tems of the 1990s. The first layer of defense in these computer security systems is provided by static access
`mechanisms, such as passwords and file permissions. Although essential, these access mechanisms are either
`too limited to provide comprehensive security, or are overly restrictive for legitimate users of the computer
`system. Several layers have been added on to the original defenses, some of the most important of these be-
`ing cryptography [Denning, 1992], which is used for implementing secure channels and host authentication,
`and firewalls [Chapman & Zwicky, 1995], which provide another layer of defense in a networked system by
`filtering out undesirable network traffic. Yet another layer of defense is provided by dynamic protection sys-
`tems that detect and prevent intrusions. These dynamic protection systems are known as Intrusion Detection
`(ID) systems [Anderson, 1980, Denning, 1987].
`These computer security systems fall short of what could be accomplished: in a survey carried out
`by the Computer Security Institute in collaboration with the Federal Bureau of Investigation, 64% of 520
`computer security practitioners surveyed reported security breaches during the 1998 financial year, a 16%
`increase from the year before [Power, 1998]. Only half of the respondents could estimate their financial
`losses from these incidents, at about 138 million dollars. According to [Power, 1998], we should assume that
`these estimates (both of losses and intrusions) are conservative, because many institutions will not be aware
`they have been compromised, and of those who become aware, few will report it. However, with all these
`dire figures, it is worth noting that only 35% of the respondents used ID systems. It is not clear why this is
`the case, whether it is that the current ID systems are not cost-effective, or simply that they are an innovation
`that has not yet been widely accepted.
`There is some indication that current ID systems are not effective enough, and suffer from lack of
`correctness. In an evaluation performed by Lincoln Laboratory in 1998, ID systems detected 50 to 70% of at-
`tacks with false alarm rates of between one and ten per day [Lippman, 1998]. Although these false alarm rates
`are acceptable according to [Lippman, 1998], the detection rates can be improved, and in particular, none of
`the systems tested was able to detect novel new intrusions. Most of these systems carried out signature-based4
`detection, meaning that they stored patterns of known intrusive behaviour and then scanned for occurrences
`of those patterns. Few systems carried out anomaly detection, where the incidents are unknown ahead of time
`(that is, they are not included in a training set), and detection is a process of scanning for deviations from
`a known normal behaviour. These systems could not detect novel intrusions because they did not perform
`anomaly detection.
`By contrast, the IS makes use of both signature-based and anomaly detection. It has mechanisms for
`detecting deviations from a set of normal patterns, and it has