Change search

Analysis and Synthesis of Boolean Networks
KTH, School of Information and Communication Technology (ICT), Electronics and Embedded Systems.ORCID iD: 0000-0003-2962-5509
2015 (English)Licentiate thesis, comprehensive summary (Other academic)
##### Abstract [en]

In this thesis, we present techniques and algorithms for analysis and synthesis of synchronous Boolean and multiple-valued networks.

Synchronous Boolean and multiple-valued networks are a discrete-space discrete-time model of gene regulatory networks. Their cycle of states, called \emph{attractors}, are believed to give a good indication of the possible functional modes of the system. This motivates research on algorithms for finding attractors. Existing decision diagram-based approaches have limited capacity due to the excessive memory requirements of decision diagrams. Simulation-based approaches can be applied to large networks, however, their results are incomplete. In the first part of this thesis, we present an algorithm, which uses a SAT-based bounded model checking approach to find all attractors in a multiple-valued network. The efficiency of the presented algorithm is evaluated by analysing 30 network models of real biological processes as well as \num{35000} randomly generated 4-valued networks. The results show that our algorithm has a potential to handle an order of magnitude larger models than currently possible. One of the characteristic features of genetic regulatory networks is their inherent robustness, that is, their ability to retain functionality in spite of the introduction of random faults. In the second part of this thesis, we focus on the robustness of a special kind of Boolean networks called \emph{Balanced Boolean Networks} (BBNs). We formalize the notion of robustness and introduce a method to construct \emph{BBNs} for $2$-singleton attractors Boolean networks. The experiment results show that \emph{BBNs} are capable of tolerating single stuck-at faults. Our method improves the robustness of random Boolean networks by at least $13\%$ on average, and in some special case, up to $61\%$.

In the third part of this thesis, we focus on a special type of synchronous Boolean networks, namely Feedback Shift Registers (FSRs). FSR-based filter generators are used as a basic building block in many cryptographic systems, e.g. stream ciphers. Filter generators are popular because their well-defined mathematical description enables a detailed formal security analysis. We show how to modify a filter generator into a nonlinear FSR, which is faster, but slightly larger, than the original filter generator. For example, the propagation delay can be reduced 1.54 times at the expense of 1.27\% extra area. The presented method might be important for applications, which require very high data rates, e.g. 5G mobile communication technology.

In the fourth part of this thesis, we present a new method for detecting and correcting transient faults in FSRs based on duplication and parity checking. Periodic fault detection of functional circuits is very important for cryptographic systems because a random hardware fault can compromise their security.

The presented method is more reliable than Triple Modular Redundancy (TMR) for large FSRs, while the area overhead of the two approaches are comparable. The presented approach might be important for cryptographic systems using large FSRs.

##### Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology, 2015. , xi, 57 p.
##### Series
TRITA-ICT, 2015:23
Computer Systems
##### Identifiers
ISBN: 978-91-7595-770-8 (print)OAI: oai:DiVA.org:kth-177138DiVA: diva2:871622
##### Presentation
2015-12-18, Sla B, Electrum, KTH-ICT, Kista, 09:00 (English)
##### Note

QC 20151120

Available from: 2015-11-20 Created: 2015-11-16 Last updated: 2015-11-20Bibliographically approved
##### List of papers
1. Finding Attractors in Synchronous Multiple-Valued Networks Using SAT-based Bounded Model Checking
Open this publication in new window or tab >>Finding Attractors in Synchronous Multiple-Valued Networks Using SAT-based Bounded Model Checking
2012 (English)In: Journal of Multiple-Valued Logic and Soft Computing, ISSN 1542-3980, E-ISSN 1542-3999, Vol. 19, no 1-3, 109-131 p.Article in journal (Refereed) Published
##### Abstract [en]

Synchronous multiple-valued networks are a discrete-space discrete-time model of the gene regulatory network of living cells. In this model, cell types are represented by the cycles in the state transition graph of a network, called attractors. When the effect of a disease or a mutation on a cell is studied, attractors have to be re-computed each time a fault is injected in the model. This motivates research on algorithms for finding attractors. Existing decision diagram-based approaches have limited capacity due to the excessive memory requirements of decision diagrams. Simulation-based approaches can be applied to larger networks, however, they are incomplete. We present an algorithm for finding attractors which uses a SAT-based bounded model checking. Our model checking approach exploits the deterministic nature of the network model to reduce runtime. Although the idea of applying model checking to the analysis of gene regulatory networks is not new, to our best knowledge, we are the first to use it for computing all attractors in a model. The efficiency of the presented algorithm is evaluated by analyzing 7 networks models of real biological processes as well as 35.000 randomly generated 4-valued networks. The results show that our approach has a potential to handle an order of magnitude larger models than currently possible.

##### Place, publisher, year, edition, pages
Old City Publishing, 2012
##### Keyword
Multiple-Valued Network, SAT, Model Checking, attractor
Natural Sciences
SRA - ICT
##### Identifiers
urn:nbn:se:kth:diva-107495 (URN)000305440000009 ()2-s2.0-84864069529 (ScopusID)
##### Note

QC 20130109

Available from: 2013-01-10 Created: 2012-12-12 Last updated: 2015-11-20Bibliographically approved
2. The robustness of balanced boolean networks
Open this publication in new window or tab >>The robustness of balanced boolean networks
2013 (English)In: Complex Networks / [ed] Menezes, Ronaldo; Evsukoff, Alexandre; González, Marta C, Springer Berlin/Heidelberg, 2013, 19-30 p.Conference paper (Refereed)
##### Abstract [en]

One of the characteristic features of genetic regulatory networks is their inherent robustness, that is, their ability to retain functionality in spite of the introduction of random errors. In this paper, we focus on the robustness of Balanced Boolean Networks (BBNs), which is a special kind of Boolean Network model of genetic regulatory networks. Our goal is to formalize and analyse the robustness of BBNs. Based on these results, applications using Boolean network model can be improved and optimized to be more robust. We formalize BBNs and introduce a method to construct BBNs for 2-singleton attractors Boolean networks. The experiment results show that BBNs have a good performance on tolerating the single stuck-at faults on every edge. Our method improves the robustness of Boolean networks by at least 13% in average, and in some special case, up to 61%.

##### Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2013
##### Series
Studies in Computational Intelligence, ISSN 1860-949X ; 424
##### National Category
Computer and Information Science
##### Identifiers
urn:nbn:se:kth:diva-118141 (URN)10.1007/978-3-642-30287-9-3 (DOI)2-s2.0-84867458405 (ScopusID)978-3-642-30287-9 (ISBN)
##### Conference
Results of the 3rd Workshop on Complex Networks Complenet 2012, Melbourne, Florida, USA March 7-9, 2012
##### Note

QC 20130215

Available from: 2013-02-15 Created: 2013-02-12 Last updated: 2015-11-20Bibliographically approved
3. A Faster Shift Register Alternative to Filter Generators
Open this publication in new window or tab >>A Faster Shift Register Alternative to Filter Generators
2013 (English)In: Proceedings - 16th Euromicro Conference on Digital System Design, DSD 2013, IEEE , 2013, 713-718 p.Conference paper (Refereed)
##### Abstract [en]

LFSR-based filter generators are used as a basic building block in many stream ciphers. Filter generators are popular because their well-defined mathematical description enables a detailed formal security analysis. In this paper, we show how to modify a filter generator into a nonlinear feedback shift register which is faster, but slightly larger, than the original filter generator. For example, the propagation delay can be reduced 1.54 times at the expense of 1.27% extra area. The presented method might be important for applications which require very high data rates, e.g. 4G mobile communication technology.

IEEE, 2013
##### Keyword
Cryptography security, NLFSR, Propagation delay
Embedded Systems
##### Identifiers
urn:nbn:se:kth:diva-138550 (URN)10.1109/DSD.2013.81 (DOI)000337235200098 ()2-s2.0-84890017929 (ScopusID)978-076955074-9 (ISBN)
##### Conference
16th Euromicro Conference on Digital System Design, DSD 2013; Santander; Spain; 4 September 2013 through 6 September 2013
##### Funder
Swedish Foundation for Strategic Research
##### Note

QC 20140305

Available from: 2013-12-19 Created: 2013-12-19 Last updated: 2015-11-20Bibliographically approved
4. A New Approach to Reliable FSRs Design
Open this publication in new window or tab >>A New Approach to Reliable FSRs Design
2014 (English)In: Proceedings of 32nd Nordic Microelectronics Conference NORCHIP , IEEE conference proceedings, 2014Conference paper (Refereed)
##### Place, publisher, year, edition, pages
IEEE conference proceedings, 2014
##### Keyword
FSR, reliability, fault-tolerance
##### National Category
Electrical Engineering, Electronic Engineering, Information Engineering
##### Identifiers
urn:nbn:se:kth:diva-165584 (URN)
##### Conference
32nd Nordic Microelectronics Conference NORCHIP
##### Funder
Swedish Foundation for Strategic Research , SM12-0005
##### Note

NQC 2015

Available from: 2015-04-29 Created: 2015-04-29 Last updated: 2015-11-20Bibliographically approved

#### Open Access in DiVA

##### File information
File name FULLTEXT01.pdfFile size 824 kBChecksum SHA-512
Type fulltextMimetype application/pdf

#### Search in DiVA

Liu, Ming
##### By organisation
Electronics and Embedded Systems
Computer Systems