On the complexity of monitoring Orchids signatures, and recurrence equations View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2018-08

AUTHORS

Jean Goubault-Larrecq, Jean-Philippe Lachance

ABSTRACT

Modern monitoring tools such as our intrusion detection tool Orchids work by firing new monitor instances dynamically. Given an Orchids signature (a.k.a. a rule, a specification), what is the complexity of checking that specification, that signature? In other words, let f(n) be the maximum number of monitor instances that can be fired on a sequence of n events: we design an algorithm that decides whether f(n) is asymptotically exponential or polynomial, and in the latter case returns an exponent d such that f(n)=Θ(nd). Ultimately, the problem reduces to the following mathematical question, which may have other uses in other domains: given a system of recurrence equations described using the operators + and max, and defining integer sequences un, what is the asymptotic behavior of un as n tends to infinity? We show that, under simple assumptions, un is either exponential or polynomial, and that this can be decided, and the exponent computed, using a simple modification of Tarjan’s strongly connected components algorithm, in linear time. More... »

PAGES

6-32

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s10703-017-0303-x

DOI

http://dx.doi.org/10.1007/s10703-017-0303-x

DIMENSIONS

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


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/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Laboratoire Sp\u00e9cification et V\u00e9rification", 
          "id": "https://www.grid.ac/institutes/grid.464035.0", 
          "name": [
            "LSV, ENS Paris-Saclay, CNRS, Universit\u00e9 Paris-Saclay, 61, avenue du pr\u00e9sident Wilson, 94230, Cachan Cedex, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Goubault-Larrecq", 
        "givenName": "Jean", 
        "id": "sg:person.014167263014.49", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014167263014.49"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "name": [
            "Coveo Solutions, Inc., G1W 2K7, Quebec City, QC, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lachance", 
        "givenName": "Jean-Philippe", 
        "id": "sg:person.013327773213.99", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013327773213.99"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/978-3-642-54862-8_10", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007587119", 
          "https://doi.org/10.1007/978-3-642-54862-8_10"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-319-05302-8_1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1016468644", 
          "https://doi.org/10.1007/978-3-319-05302-8_1"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10817-010-9174-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1023433013", 
          "https://doi.org/10.1007/s10817-010-9174-1"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10817-010-9174-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1023433013", 
          "https://doi.org/10.1007/s10817-010-9174-1"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-319-12736-1_15", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027464080", 
          "https://doi.org/10.1007/978-3-319-12736-1_15"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/2699444", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1036398147"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-319-11164-3_24", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045022553", 
          "https://doi.org/10.1007/978-3-319-11164-3_24"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-89247-2_1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1047722511", 
          "https://doi.org/10.1007/978-3-540-89247-2_1"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-89247-2_1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1047722511", 
          "https://doi.org/10.1007/978-3-540-89247-2_1"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11513988_28", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052212471", 
          "https://doi.org/10.1007/11513988_28"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11513988_28", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052212471", 
          "https://doi.org/10.1007/11513988_28"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0201010", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062841173"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-658-09994-7_6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1085931492", 
          "https://doi.org/10.1007/978-3-658-09994-7_6"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/csfw.2001.930148", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1093369065"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/icse.2012.6227231", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1095618770"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1017/cbo9780511801655", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1098667872"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2018-08", 
    "datePublishedReg": "2018-08-01", 
    "description": "Modern monitoring tools such as our intrusion detection tool Orchids work by firing new monitor instances dynamically. Given an Orchids signature (a.k.a. a rule, a specification), what is the complexity of checking that specification, that signature? In other words, let f(n) be the maximum number of monitor instances that can be fired on a sequence of n events: we design an algorithm that decides whether f(n) is asymptotically exponential or polynomial, and in the latter case returns an exponent d such that f(n)=\u0398(nd). Ultimately, the problem reduces to the following mathematical question, which may have other uses in other domains: given a system of recurrence equations described using the operators + and max, and defining integer sequences un, what is the asymptotic behavior of un as n tends to infinity? We show that, under simple assumptions, un is either exponential or polynomial, and that this can be decided, and the exponent computed, using a simple modification of Tarjan\u2019s strongly connected components algorithm, in linear time.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s10703-017-0303-x", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1052628", 
        "issn": [
          "0925-9856", 
          "1572-8102"
        ], 
        "name": "Formal Methods in System Design", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "53"
      }
    ], 
    "name": "On the complexity of monitoring Orchids signatures, and recurrence equations", 
    "pagination": "6-32", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "1cf1d493a009f708f9036e8b394f545a632e04f62f097ed59fda955aa2226088"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s10703-017-0303-x"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1092416264"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s10703-017-0303-x", 
      "https://app.dimensions.ai/details/publication/pub.1092416264"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T02:30", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8700_00000601.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://link.springer.com/10.1007%2Fs10703-017-0303-x"
  }
]
 

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/s10703-017-0303-x'

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/s10703-017-0303-x'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10703-017-0303-x'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10703-017-0303-x'


 

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

117 TRIPLES      21 PREDICATES      40 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s10703-017-0303-x schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N3d4e436214254ee18d70253159b7aa50
4 schema:citation sg:pub.10.1007/11513988_28
5 sg:pub.10.1007/978-3-319-05302-8_1
6 sg:pub.10.1007/978-3-319-11164-3_24
7 sg:pub.10.1007/978-3-319-12736-1_15
8 sg:pub.10.1007/978-3-540-89247-2_1
9 sg:pub.10.1007/978-3-642-54862-8_10
10 sg:pub.10.1007/978-3-658-09994-7_6
11 sg:pub.10.1007/s10817-010-9174-1
12 https://doi.org/10.1017/cbo9780511801655
13 https://doi.org/10.1109/csfw.2001.930148
14 https://doi.org/10.1109/icse.2012.6227231
15 https://doi.org/10.1137/0201010
16 https://doi.org/10.1145/2699444
17 schema:datePublished 2018-08
18 schema:datePublishedReg 2018-08-01
19 schema:description Modern monitoring tools such as our intrusion detection tool Orchids work by firing new monitor instances dynamically. Given an Orchids signature (a.k.a. a rule, a specification), what is the complexity of checking that specification, that signature? In other words, let f(n) be the maximum number of monitor instances that can be fired on a sequence of n events: we design an algorithm that decides whether f(n) is asymptotically exponential or polynomial, and in the latter case returns an exponent d such that f(n)=Θ(nd). Ultimately, the problem reduces to the following mathematical question, which may have other uses in other domains: given a system of recurrence equations described using the operators + and max, and defining integer sequences un, what is the asymptotic behavior of un as n tends to infinity? We show that, under simple assumptions, un is either exponential or polynomial, and that this can be decided, and the exponent computed, using a simple modification of Tarjan’s strongly connected components algorithm, in linear time.
20 schema:genre research_article
21 schema:inLanguage en
22 schema:isAccessibleForFree false
23 schema:isPartOf N461f77bd8f3644a09ca7d66ee025b8a3
24 N711bcc52391f46a4af23c261d5f87f38
25 sg:journal.1052628
26 schema:name On the complexity of monitoring Orchids signatures, and recurrence equations
27 schema:pagination 6-32
28 schema:productId N0965318ccfbd4783ba7f6469b1044bab
29 N3e06ed9d1cfc4b0ca972a57312226452
30 Nb872f4f933dd433ea402e07b4d939779
31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1092416264
32 https://doi.org/10.1007/s10703-017-0303-x
33 schema:sdDatePublished 2019-04-11T02:30
34 schema:sdLicense https://scigraph.springernature.com/explorer/license/
35 schema:sdPublisher Nff170c53bfba45628d7cc00d8ce5c581
36 schema:url https://link.springer.com/10.1007%2Fs10703-017-0303-x
37 sgo:license sg:explorer/license/
38 sgo:sdDataset articles
39 rdf:type schema:ScholarlyArticle
40 N0965318ccfbd4783ba7f6469b1044bab schema:name dimensions_id
41 schema:value pub.1092416264
42 rdf:type schema:PropertyValue
43 N3d4e436214254ee18d70253159b7aa50 rdf:first sg:person.014167263014.49
44 rdf:rest Na12d6e510b0e4126969a12e7137545e8
45 N3e06ed9d1cfc4b0ca972a57312226452 schema:name doi
46 schema:value 10.1007/s10703-017-0303-x
47 rdf:type schema:PropertyValue
48 N461f77bd8f3644a09ca7d66ee025b8a3 schema:issueNumber 1
49 rdf:type schema:PublicationIssue
50 N711bcc52391f46a4af23c261d5f87f38 schema:volumeNumber 53
51 rdf:type schema:PublicationVolume
52 N797e9eedcdcf4a17be0105eda7891dd3 schema:name Coveo Solutions, Inc., G1W 2K7, Quebec City, QC, Canada
53 rdf:type schema:Organization
54 Na12d6e510b0e4126969a12e7137545e8 rdf:first sg:person.013327773213.99
55 rdf:rest rdf:nil
56 Nb872f4f933dd433ea402e07b4d939779 schema:name readcube_id
57 schema:value 1cf1d493a009f708f9036e8b394f545a632e04f62f097ed59fda955aa2226088
58 rdf:type schema:PropertyValue
59 Nff170c53bfba45628d7cc00d8ce5c581 schema:name Springer Nature - SN SciGraph project
60 rdf:type schema:Organization
61 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
62 schema:name Mathematical Sciences
63 rdf:type schema:DefinedTerm
64 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
65 schema:name Pure Mathematics
66 rdf:type schema:DefinedTerm
67 sg:journal.1052628 schema:issn 0925-9856
68 1572-8102
69 schema:name Formal Methods in System Design
70 rdf:type schema:Periodical
71 sg:person.013327773213.99 schema:affiliation N797e9eedcdcf4a17be0105eda7891dd3
72 schema:familyName Lachance
73 schema:givenName Jean-Philippe
74 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013327773213.99
75 rdf:type schema:Person
76 sg:person.014167263014.49 schema:affiliation https://www.grid.ac/institutes/grid.464035.0
77 schema:familyName Goubault-Larrecq
78 schema:givenName Jean
79 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014167263014.49
80 rdf:type schema:Person
81 sg:pub.10.1007/11513988_28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052212471
82 https://doi.org/10.1007/11513988_28
83 rdf:type schema:CreativeWork
84 sg:pub.10.1007/978-3-319-05302-8_1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016468644
85 https://doi.org/10.1007/978-3-319-05302-8_1
86 rdf:type schema:CreativeWork
87 sg:pub.10.1007/978-3-319-11164-3_24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045022553
88 https://doi.org/10.1007/978-3-319-11164-3_24
89 rdf:type schema:CreativeWork
90 sg:pub.10.1007/978-3-319-12736-1_15 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027464080
91 https://doi.org/10.1007/978-3-319-12736-1_15
92 rdf:type schema:CreativeWork
93 sg:pub.10.1007/978-3-540-89247-2_1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047722511
94 https://doi.org/10.1007/978-3-540-89247-2_1
95 rdf:type schema:CreativeWork
96 sg:pub.10.1007/978-3-642-54862-8_10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007587119
97 https://doi.org/10.1007/978-3-642-54862-8_10
98 rdf:type schema:CreativeWork
99 sg:pub.10.1007/978-3-658-09994-7_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1085931492
100 https://doi.org/10.1007/978-3-658-09994-7_6
101 rdf:type schema:CreativeWork
102 sg:pub.10.1007/s10817-010-9174-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023433013
103 https://doi.org/10.1007/s10817-010-9174-1
104 rdf:type schema:CreativeWork
105 https://doi.org/10.1017/cbo9780511801655 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098667872
106 rdf:type schema:CreativeWork
107 https://doi.org/10.1109/csfw.2001.930148 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093369065
108 rdf:type schema:CreativeWork
109 https://doi.org/10.1109/icse.2012.6227231 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095618770
110 rdf:type schema:CreativeWork
111 https://doi.org/10.1137/0201010 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841173
112 rdf:type schema:CreativeWork
113 https://doi.org/10.1145/2699444 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036398147
114 rdf:type schema:CreativeWork
115 https://www.grid.ac/institutes/grid.464035.0 schema:alternateName Laboratoire Spécification et Vérification
116 schema:name LSV, ENS Paris-Saclay, CNRS, Université Paris-Saclay, 61, avenue du président Wilson, 94230, Cachan Cedex, France
117 rdf:type schema:Organization
 




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


...