Computing, School of
http://hdl.handle.net/1974/771
Wed, 16 Aug 2017 11:36:50 GMT2017-08-16T11:36:50ZDiscovery of Patterns in Simulink Systems
http://hdl.handle.net/1974/20102
Discovery of Patterns in Simulink Systems
de la Parra, Francisco
Model-Driven Engineering tools and techniques have become mainstream aids in the development
of embedded cyber-physical systems. The large-scale use of visual models is a powerful
paradigm for designing reliable and maintainable systems assembled with complex hardware, software
and mechanical elements. Modular design approaches can readily capture the requirements
for embedded systems into executable and evolutionary models.
We propose a framework to discover, classify and visualize model-patterns in large repositories of
Simulink models. We design, and implement in a software toolchain, a set of scalable algorithms to
fully traverse and contextually parse the source code of these repositories in order to compute topology
hash functions for the size, name connectivity and type connectivity of each model subsystem,
as well as properties of Stateflow charts. We use these extracted properties to cluster the subsystems
into a set of addressable-by-property classes. We develop an interactive model visualization and
querying facility, embodied by the MoSART user interface, to identify further relations, similarities
and abstractions in the elements of the cluster classes. This tool provides a configurable environment
for inferring structural model-patterns and elaborating on semantic model-patterns with the assistance
of skilled domain knowledge. We propose a query system, based on regular expressions that
match values of previously computed subsystems properties, as an effective method to iteratively
refine Simulink model-patterns abstractions into accumulated modeling knowledge.
Our implementation works cooperatively with a 3-phase iterative model-pattern discovery approach
that we conceptualize as 1) model clustering: repository traversal and subsystem-topology
evaluation for clustering subsystems, 2) primary model-pattern inference: visualization, querybased
search and clustering for identifying basic semantic patterns, 3) model-pattern refinement:
continuous refinement of basic patterns into specialized groups for application in targeted use cases.
We effectively support the iterative nature of this approach because our repository traversal, property
evaluation and clustering algorithms have low time-complexity, that is, between a lower-bound(n) and
O(n lg n)(n = total lines of source code in a repository), and our interactive tool provides a
complete-coverage view of a model repository.
http://hdl.handle.net/1974/20102State complexity of deletion and bipolar deletion
http://hdl.handle.net/1974/15961
State complexity of deletion and bipolar deletion
Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai
It is well known that the language obtained
by deleting an arbitrary
language from a regular language is regular.
We give an upper bound for the
state complexity of deleting an arbitrary
language from a regular language and a matching
lower bound.
We show that the state complexity of deletion
is $n \cdot 2^{n-1}$ (respectively, $(n + \frac{1}{2}) \cdot 2^n - 2$)
when using complete (respectively, incomplete) deterministic
finite automata.
We show that the state complexity of bipolar deletion
has an upper bound $n^n$ (respectively $(n+1)^n - 1$)
when using complete (respectively, incomplete)
deterministic finite automata. In both cases we give
almost matching lower bounds.
Fri, 01 Jan 2016 00:00:00 GMThttp://hdl.handle.net/1974/159612016-01-01T00:00:00ZDescriptional complexity of unambiguous input-driven pushdown automata
http://hdl.handle.net/1974/15960
Descriptional complexity of unambiguous input-driven pushdown automata
Okhotin, Alexander; Salomaa, Kai
It is known that
a nondeterministic input-driven pushdown automaton (IDPDA)
(a.k.a.~visibly pushdown automaton;
a.k.a.~nested word automaton) of size $n$
can be transformed to an equivalent deterministic automaton
of size $2^{\Theta(n^2)}$
(B. von Braunm\"uhl, R. Verbeek,
\href{http://dx.doi.org/10.1016/S0304-0208(08)73072-X}
{``Input-driven languages are recognized in $\log n$ space''},
FCT 1983),
and that this size is necessary in the worst case
(R. Alur, P. Madhusudan,
\href{http://dx.doi.org/10.1145/1516512.1516518}
{``Adding nesting structure to words''},
J.ACM, 2009).
This paper demonstrates
that the same worst-case $2^{\Theta(n^2)}$ size blow-up
occurs when converting
a nondeterministic IDPDA to an unambiguous one,
and an unambiguous IDPDA to a deterministic one.
In addition, the methods developed in this paper
are used to demonstrate
that the descriptional complexity of complementation
for nondeterministic IDPDAs
is $2^{\Theta(n^2)}$,
and that the descriptional complexity of homomorphisms
for deterministic IDPDAs
is $2^{\Theta(n^2)}$ as well.
Wed, 01 Apr 2015 00:00:00 GMThttp://hdl.handle.net/1974/159602015-04-01T00:00:00ZA Protocol-Specific Constraint-Based Intrusion Detection System
http://hdl.handle.net/1974/15950
A Protocol-Specific Constraint-Based Intrusion Detection System
Hasan, Md
With the advancement of new technologies, the frequency of malicious attacks is also growing rapidly. Even networks without external connections cannot hide from these attacks. Constant monitoring of a network is vital for an organization's security system. Among numerous monitoring techniques, network behavior analysis has become popular. Normal traffic patterns of a network can be modeled as network constraints. The violation of these constraints indicates the possibility that an intrusion has occurred.
Expressing network vulnerabilities is not an easy task. Sometimes, it is more complicated than recognizing an intruder's attack pattern. Currently, network administrators use Intrusion Detection System (IDS) rules to define security concerns regarding their networks. An IDS rule finds it difficult to detect sophisticated multi-packet intrusions. Constraints compared to IDS rules possess better expressiveness to describe a network behavior for defending the network against different attacks.
Evaluating constraints in an efficient manner is a key to achieving a better IDS. Numerous constraint checking techniques provide good performance in solving constraints. However, they are not always effective in checking constraints with dynamic information.
In this thesis, we propose a protocol specific constraint-based IDS to detect intrusions in a network. We investigate two protocols used in the Data Distribution Service (DDS) and identify their vulnerabilities. These two protocols are Internet Group Management Protocol (IGMP) and Real-Time Publisher Subscriber Protocol (RTPS). We develop constraints to protect a network against attacks that may exploit these vulnerabilities. For checking these constraints, a naive tree-based technique along with an optimized version is presented. Both techniques have the adaptability to cope with a continuous update of relevant network behavior information from a network traffic. The structure and life cycle of the constraint trees are explained in detail. A Domain Specific Language (DSL) is designed to express these constraints. An experimental private network is built which simulates network traffic similar to an Air Traffic Control System (ATC). Finally, we present how this IDS evaluates network constraints against the traffic generated from the experimental network and prevents attacks.
http://hdl.handle.net/1974/15950