View in EDS

Active learning for extended finite state machines.

Saved in:
Bibliographic Details
Title: Active learning for extended finite state machines.
Authors: Cassel, Sofia1 sofia.cassel@it.uu.se, Howar, Falk2, Jonsson, Bengt1, Steffen, Bernhard3
Source: Formal Aspects of Computing. Apr2016, Vol. 28 Issue 2, p233-263. 31p.
Subjects: Finite state machines, Data flow computing, Active learning, Generalization, Machine learning
Abstract: We present a black-box active learning algorithm for inferring extended finite state machines (EFSM)s by dynamic black-box analysis. EFSMs can be used to model both data flow and control behavior of software and hardware components. Different dialects of EFSMs are widely used in tools for model-based software development, verification, and testing. Our algorithm infers a class of EFSMs called register automata. Register automata have a finite control structure, extended with variables (registers), assignments, and guards. Our algorithm is parameterized on a particular theory, i.e., a set of operations and tests on the data domain that can be used in guards. Key to our learning technique is a novel learning model based on so-called tree queries. The learning algorithm uses tree queries to infer symbolic data constraints on parameters, e.g., sequence numbers, time stamps, identifiers, or even simple arithmetic. We describe sufficient conditions for the properties that the symbolic constraints provided by a tree query in general must have to be usable in our learning model. We also show that, under these conditions, our framework induces a generalization of the classical Nerode equivalence and canonical automata construction to the symbolic setting. We have evaluated our algorithm in a black-box scenario, where tree queries are realized through (black-box) testing. Our case studies include connection establishment in TCP and a priority queue from the Java Class Library. [ABSTRACT FROM AUTHOR]
Copyright of Formal Aspects of Computing is the property of Association for Computing Machinery and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 114327193
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Active learning for extended finite state machines.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Cassel%2C+Sofia%22">Cassel, Sofia</searchLink><relatesTo>1</relatesTo><i> sofia.cassel@it.uu.se</i><br /><searchLink fieldCode="AR" term="%22Howar%2C+Falk%22">Howar, Falk</searchLink><relatesTo>2</relatesTo><br /><searchLink fieldCode="AR" term="%22Jonsson%2C+Bengt%22">Jonsson, Bengt</searchLink><relatesTo>1</relatesTo><br /><searchLink fieldCode="AR" term="%22Steffen%2C+Bernhard%22">Steffen, Bernhard</searchLink><relatesTo>3</relatesTo>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Formal+Aspects+of+Computing%22">Formal Aspects of Computing</searchLink>. Apr2016, Vol. 28 Issue 2, p233-263. 31p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Finite+state+machines%22">Finite state machines</searchLink><br /><searchLink fieldCode="DE" term="%22Data+flow+computing%22">Data flow computing</searchLink><br /><searchLink fieldCode="DE" term="%22Active+learning%22">Active learning</searchLink><br /><searchLink fieldCode="DE" term="%22Generalization%22">Generalization</searchLink><br /><searchLink fieldCode="DE" term="%22Machine+learning%22">Machine learning</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: We present a black-box active learning algorithm for inferring extended finite state machines (EFSM)s by dynamic black-box analysis. EFSMs can be used to model both data flow and control behavior of software and hardware components. Different dialects of EFSMs are widely used in tools for model-based software development, verification, and testing. Our algorithm infers a class of EFSMs called register automata. Register automata have a finite control structure, extended with variables (registers), assignments, and guards. Our algorithm is parameterized on a particular theory, i.e., a set of operations and tests on the data domain that can be used in guards. Key to our learning technique is a novel learning model based on so-called tree queries. The learning algorithm uses tree queries to infer symbolic data constraints on parameters, e.g., sequence numbers, time stamps, identifiers, or even simple arithmetic. We describe sufficient conditions for the properties that the symbolic constraints provided by a tree query in general must have to be usable in our learning model. We also show that, under these conditions, our framework induces a generalization of the classical Nerode equivalence and canonical automata construction to the symbolic setting. We have evaluated our algorithm in a black-box scenario, where tree queries are realized through (black-box) testing. Our case studies include connection establishment in TCP and a priority queue from the Java Class Library. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Formal Aspects of Computing is the property of Association for Computing Machinery and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=114327193
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1007/s00165-016-0355-5
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 31
        StartPage: 233
    Subjects:
      – SubjectFull: Finite state machines
        Type: general
      – SubjectFull: Data flow computing
        Type: general
      – SubjectFull: Active learning
        Type: general
      – SubjectFull: Generalization
        Type: general
      – SubjectFull: Machine learning
        Type: general
    Titles:
      – TitleFull: Active learning for extended finite state machines.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Cassel, Sofia
      – PersonEntity:
          Name:
            NameFull: Howar, Falk
      – PersonEntity:
          Name:
            NameFull: Jonsson, Bengt
      – PersonEntity:
          Name:
            NameFull: Steffen, Bernhard
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 04
              Text: Apr2016
              Type: published
              Y: 2016
          Identifiers:
            – Type: issn-print
              Value: 09345043
          Numbering:
            – Type: volume
              Value: 28
            – Type: issue
              Value: 2
          Titles:
            – TitleFull: Formal Aspects of Computing
              Type: main
ResultId 1