Detection of Interactive Stepping Stones: Algorithms and Confidence Bounds View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2004

AUTHORS

Avrim Blum , Dawn Song , Shobha Venkataraman

ABSTRACT

Intruders on the Internet often prefer to launch network intrusions indirectly, i.e., using a chain of hosts on the Internet as relay machines using protocols such as Telnet or SSH. This type of attack is called a stepping-stone attack. In this paper, we propose and analyze algorithms for stepping-stone detection using ideas from Computational Learning Theory and the analysis of random walks. Our results are the first to achieve provable (polynomial) upper bounds on the number of packets needed to confidently detect and identify encrypted stepping-stone streams with proven guarantees on the probability of falsely accusing non-attacking pairs. Moreover, our methods and analysis rely on mild assumptions, especially in comparison to previous work. We also examine the consequences when the attacker inserts chaff into the stepping-stone traffic, and give bounds on the amount of chaff that an attacker would have to send to evade detection. Our results are based on a new approach which can detect correlation of streams at a fine-grained level. Our approach may also apply to more generalized traffic analysis domains, such as anonymous communication. More... »

PAGES

258-277

Book

TITLE

Recent Advances in Intrusion Detection

ISBN

978-3-540-23123-3
978-3-540-30143-1

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-30143-1_14

DOI

http://dx.doi.org/10.1007/978-3-540-30143-1_14

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1024781003


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Carnegie Mellon University, 15213, Pittsburgh, PA, USA", 
          "id": "http://www.grid.ac/institutes/grid.147455.6", 
          "name": [
            "Carnegie Mellon University, 15213, Pittsburgh, PA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Blum", 
        "givenName": "Avrim", 
        "id": "sg:person.010510241243.49", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010510241243.49"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Carnegie Mellon University, 15213, Pittsburgh, PA, USA", 
          "id": "http://www.grid.ac/institutes/grid.147455.6", 
          "name": [
            "Carnegie Mellon University, 15213, Pittsburgh, PA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Song", 
        "givenName": "Dawn", 
        "id": "sg:person.01143152610.86", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01143152610.86"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Carnegie Mellon University, 15213, Pittsburgh, PA, USA", 
          "id": "http://www.grid.ac/institutes/grid.147455.6", 
          "name": [
            "Carnegie Mellon University, 15213, Pittsburgh, PA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Venkataraman", 
        "givenName": "Shobha", 
        "type": "Person"
      }
    ], 
    "datePublished": "2004", 
    "datePublishedReg": "2004-01-01", 
    "description": "Intruders on the Internet often prefer to launch network intrusions indirectly, i.e., using a chain of hosts on the Internet as relay machines using protocols such as Telnet or SSH. This type of attack is called a stepping-stone attack. In this paper, we propose and analyze algorithms for stepping-stone detection using ideas from Computational Learning Theory and the analysis of random walks. Our results are the first to achieve provable (polynomial) upper bounds on the number of packets needed to confidently detect and identify encrypted stepping-stone streams with proven guarantees on the probability of falsely accusing non-attacking pairs. Moreover, our methods and analysis rely on mild assumptions, especially in comparison to previous work. We also examine the consequences when the attacker inserts chaff into the stepping-stone traffic, and give bounds on the amount of chaff that an attacker would have to send to evade detection. Our results are based on a new approach which can detect correlation of streams at a fine-grained level. Our approach may also apply to more generalized traffic analysis domains, such as anonymous communication.", 
    "editor": [
      {
        "familyName": "Jonsson", 
        "givenName": "Erland", 
        "type": "Person"
      }, 
      {
        "familyName": "Valdes", 
        "givenName": "Alfonso", 
        "type": "Person"
      }, 
      {
        "familyName": "Almgren", 
        "givenName": "Magnus", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-30143-1_14", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-23123-3", 
        "978-3-540-30143-1"
      ], 
      "name": "Recent Advances in Intrusion Detection", 
      "type": "Book"
    }, 
    "keywords": [
      "types of attacks", 
      "computational learning theory", 
      "stepping-stone attacks", 
      "provable upper bounds", 
      "number of packets", 
      "network intrusions", 
      "relay machine", 
      "anonymous communication", 
      "random walk", 
      "mild assumptions", 
      "amount of chaff", 
      "upper bounds", 
      "analysis domain", 
      "confidence bounds", 
      "attacker", 
      "bounds", 
      "Internet", 
      "algorithm", 
      "learning theory", 
      "attacks", 
      "new approach", 
      "previous work", 
      "Telnet", 
      "stepping stone", 
      "packets", 
      "intruders", 
      "machine", 
      "detection", 
      "guarantees", 
      "streams", 
      "traffic", 
      "walk", 
      "SSH", 
      "communication", 
      "theory", 
      "probability", 
      "protocol", 
      "approach", 
      "assumption", 
      "idea", 
      "domain", 
      "work", 
      "results", 
      "intrusion", 
      "method", 
      "number", 
      "analysis", 
      "pairs", 
      "chaff", 
      "chain", 
      "amount", 
      "comparison", 
      "types", 
      "correlation", 
      "consequences", 
      "host", 
      "levels", 
      "stones", 
      "paper"
    ], 
    "name": "Detection of Interactive Stepping Stones: Algorithms and Confidence Bounds", 
    "pagination": "258-277", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1024781003"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-30143-1_14"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-30143-1_14", 
      "https://app.dimensions.ai/details/publication/pub.1024781003"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:45", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_305.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-30143-1_14"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-30143-1_14'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-30143-1_14'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-30143-1_14'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-30143-1_14'


 

This table displays all metadata directly associated to this object as RDF triples.

142 TRIPLES      23 PREDICATES      85 URIs      78 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-30143-1_14 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author N0507353e6a66424882c70c4cd2d69638
4 schema:datePublished 2004
5 schema:datePublishedReg 2004-01-01
6 schema:description Intruders on the Internet often prefer to launch network intrusions indirectly, i.e., using a chain of hosts on the Internet as relay machines using protocols such as Telnet or SSH. This type of attack is called a stepping-stone attack. In this paper, we propose and analyze algorithms for stepping-stone detection using ideas from Computational Learning Theory and the analysis of random walks. Our results are the first to achieve provable (polynomial) upper bounds on the number of packets needed to confidently detect and identify encrypted stepping-stone streams with proven guarantees on the probability of falsely accusing non-attacking pairs. Moreover, our methods and analysis rely on mild assumptions, especially in comparison to previous work. We also examine the consequences when the attacker inserts chaff into the stepping-stone traffic, and give bounds on the amount of chaff that an attacker would have to send to evade detection. Our results are based on a new approach which can detect correlation of streams at a fine-grained level. Our approach may also apply to more generalized traffic analysis domains, such as anonymous communication.
7 schema:editor N2f1d4c79e22b46a79fe8086dcbec1e8b
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N95df80d3e8db4676a8d3f0ca7f55f400
12 schema:keywords Internet
13 SSH
14 Telnet
15 algorithm
16 amount
17 amount of chaff
18 analysis
19 analysis domain
20 anonymous communication
21 approach
22 assumption
23 attacker
24 attacks
25 bounds
26 chaff
27 chain
28 communication
29 comparison
30 computational learning theory
31 confidence bounds
32 consequences
33 correlation
34 detection
35 domain
36 guarantees
37 host
38 idea
39 intruders
40 intrusion
41 learning theory
42 levels
43 machine
44 method
45 mild assumptions
46 network intrusions
47 new approach
48 number
49 number of packets
50 packets
51 pairs
52 paper
53 previous work
54 probability
55 protocol
56 provable upper bounds
57 random walk
58 relay machine
59 results
60 stepping stone
61 stepping-stone attacks
62 stones
63 streams
64 theory
65 traffic
66 types
67 types of attacks
68 upper bounds
69 walk
70 work
71 schema:name Detection of Interactive Stepping Stones: Algorithms and Confidence Bounds
72 schema:pagination 258-277
73 schema:productId N41fc71f2d1bf4f5aae843140f29ab5ae
74 Nc6f6eaf1cb9748d2823213c1c6639f72
75 schema:publisher N7947bc4e07624b259fef24d7b68566e4
76 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024781003
77 https://doi.org/10.1007/978-3-540-30143-1_14
78 schema:sdDatePublished 2022-05-20T07:45
79 schema:sdLicense https://scigraph.springernature.com/explorer/license/
80 schema:sdPublisher N3c1e82f5ebc3432e8256494b1ac66a1c
81 schema:url https://doi.org/10.1007/978-3-540-30143-1_14
82 sgo:license sg:explorer/license/
83 sgo:sdDataset chapters
84 rdf:type schema:Chapter
85 N0507353e6a66424882c70c4cd2d69638 rdf:first sg:person.010510241243.49
86 rdf:rest N79eab68468a242b89eb1a12405348e8e
87 N2f1d4c79e22b46a79fe8086dcbec1e8b rdf:first N715fb3c309ef49c196fe9515f76fd520
88 rdf:rest N94016d2acb7a426e8384486f3a76e23d
89 N3c1e82f5ebc3432e8256494b1ac66a1c schema:name Springer Nature - SN SciGraph project
90 rdf:type schema:Organization
91 N3c3cefde0086467983b00f54c2f74694 schema:affiliation grid-institutes:grid.147455.6
92 schema:familyName Venkataraman
93 schema:givenName Shobha
94 rdf:type schema:Person
95 N40707f97897d4dffbbbaf7608f903742 schema:familyName Almgren
96 schema:givenName Magnus
97 rdf:type schema:Person
98 N41fc71f2d1bf4f5aae843140f29ab5ae schema:name dimensions_id
99 schema:value pub.1024781003
100 rdf:type schema:PropertyValue
101 N6c1f7ef6f5fe4798adf036b302ec79d9 schema:familyName Valdes
102 schema:givenName Alfonso
103 rdf:type schema:Person
104 N715fb3c309ef49c196fe9515f76fd520 schema:familyName Jonsson
105 schema:givenName Erland
106 rdf:type schema:Person
107 N7947bc4e07624b259fef24d7b68566e4 schema:name Springer Nature
108 rdf:type schema:Organisation
109 N79eab68468a242b89eb1a12405348e8e rdf:first sg:person.01143152610.86
110 rdf:rest Nad6e861aebb64b46b53334f4759dd99b
111 N94016d2acb7a426e8384486f3a76e23d rdf:first N6c1f7ef6f5fe4798adf036b302ec79d9
112 rdf:rest Nbd45f5c865d24621a81b36172c8e0224
113 N95df80d3e8db4676a8d3f0ca7f55f400 schema:isbn 978-3-540-23123-3
114 978-3-540-30143-1
115 schema:name Recent Advances in Intrusion Detection
116 rdf:type schema:Book
117 Nad6e861aebb64b46b53334f4759dd99b rdf:first N3c3cefde0086467983b00f54c2f74694
118 rdf:rest rdf:nil
119 Nbd45f5c865d24621a81b36172c8e0224 rdf:first N40707f97897d4dffbbbaf7608f903742
120 rdf:rest rdf:nil
121 Nc6f6eaf1cb9748d2823213c1c6639f72 schema:name doi
122 schema:value 10.1007/978-3-540-30143-1_14
123 rdf:type schema:PropertyValue
124 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
125 schema:name Information and Computing Sciences
126 rdf:type schema:DefinedTerm
127 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
128 schema:name Artificial Intelligence and Image Processing
129 rdf:type schema:DefinedTerm
130 sg:person.010510241243.49 schema:affiliation grid-institutes:grid.147455.6
131 schema:familyName Blum
132 schema:givenName Avrim
133 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010510241243.49
134 rdf:type schema:Person
135 sg:person.01143152610.86 schema:affiliation grid-institutes:grid.147455.6
136 schema:familyName Song
137 schema:givenName Dawn
138 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01143152610.86
139 rdf:type schema:Person
140 grid-institutes:grid.147455.6 schema:alternateName Carnegie Mellon University, 15213, Pittsburgh, PA, USA
141 schema:name Carnegie Mellon University, 15213, Pittsburgh, PA, USA
142 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...